Hinweis: von 2002 bis 2005 entstanden die Arbeiten vornehmlich nicht an der Universität Trier; die Liste enthält daher bis 2005 ausschließlich Arbeiten, an denen HF beteiligt war. Ab 2006 sind die Arbeiten aufgeführt, an denen Mitarbeiter der Professur beteiligt waren.
Hinweis: Teilweise kann man die zitierten Arbeiten erhalten, indem man einem Link folgt. Dies dient lediglich dem schnellen Zugriff für andere Wissenschaftler und mitnichten irgendwelchen kommerziellen Zwecken. Etwaige Copyright-Ansprüche bleiben davon unberührt. Daher sind manchmal auch nur die Einreichversionen der Arbeiten ins Netz gestellt worden, die verbesserten Fassungen finden sich bei den Verlagen.
Notice: Some papers are available on-line. This is a service to the scientific community and does not affect any copyright issues. Therefore, sometimes only the submitted versions have been put online. The final versions can be obtained from the publishers.
2015
D. Meister. Using swaps and deletes to make strings match. Theoretical Computer Science, 562:606-620, 2015.
P. Heggernes, P. van 't Hof, D. Meister, Y. Villanger. Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs. Theoretical Computer Science, 562:252-269, 2015.
Sergio Bermudo, Henning Fernau. Combinatorics for Smaller Kernels: The Differential of a Graph. Theoretical Computer Science, 562:330-345, 2015.
H. Fernau, F. V. Fomin, G. Philip, and S. Saurabh. On the parameterized complexity of vertex cover and edge cover with connectivity constraints. Theoretical Computer Science, 565:1–15, 2015.
H. Fernau, P. Heggernes and Y. Villanger. A multi-parameter analysis of hard problems on Deterministic Finite Automata. Journal of Computer and System Sciences, 81: 747–765, 2015.
H. Fernau, P. Heggernes, P. van ’t Hof, D. Meister, and R. Saei. Computing the metric dimension for chain graphs. Information Processing Letters, 115(9):671–676, 2015.
H. Fernau, A. López-Ortiz, and J. Romero. Kernelization algorithms for packing problems allowing overlaps. In R. Jain, S. Jain, and F. Stephan, editors, Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, volume 9076 of LNCS, pages 415–427. Springer, 2015.
H. Fernau, A. López-Ortiz, and J. Romero. Using parametric transformations toward polynomial kernels for packing problems allowing overlaps. ACM Transactions on Computation Theory, 7(3), 2015. Article 13.
H. Fernau, F. Manea, R. Mercaş, and M. L. Schmid. Pattern Matching with Variables: Fast Algorithms and New Hardness Results. In E. W. Mayr and N. Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 302–315. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2015.
D. Meister and U. Rotics. Clique-width of full bubble model graphs. Discrete Applied Mathematics, 185:138–167, 2015.
2014
D. Reidenbach and M. L. Schmid. Regular and context-free pattern languages over small alphabets. Theoretical Computer Science, 518:80-95, 2014.
S. Bermudo and H. Fernau. Computing the differential of a graph: hardness, approximability and exact algorithms. Discrete Applied Mathematics, 165:69-82, 2014.
D. Binkele-Raible, G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, and J. Rothe. The complexity of probabilistic lobbying. Discrete Optimization, 11:1-21, 2014.
H. Fernau and D. Meister. Digraphs of bounded elimination width. Discrete Applied Mathematics, 168:78-87, 2014.
D. Binkele-Raible and H. Fernau. A parameterized measure-and-conquer analysis for finding a k-leaf spanning tree in an undirected graph. Discrete Mathematics and Theoretical Computer Science, 16(1):179–200, 2014.
H. Fernau and J. A. Rodríguez-Velázquez. Notions of metric dimension of corona products: combinatorial and computational results. In E. Hirsch et al., editors, Computer Science in Russia, CSR, volume 8476 of LNCS, pages 153-166. Springer, 2014.
H. Fernau and J. A. Rodríguez-Velázquez. A survey on alliances and related parameters in graphs. Electronic Journal of Graph Theory and Applications, 2(1):70–86, 2014.
S. Bermudo, H. Fernau, and J. M. Sigarreta. The differential and the Roman domination number of a graph. Applicable Analysis and Discrete Mathematics, 8:155-171, 2014.
H. Fernau, R. Freund, and M. Holzer. Cooperating distributed grammar systems of finite index working in hybrid modes. In Z. Ésik and Z. Fülöp, editors, Proceedings 14th International Conference on Automata and Formal Languages, AFL, volume 151 of EPTCS, pages 246–260, 2014.
K. Casel. A fixed-parameter approach for privacy-protection with global recoding. In J. Chen, J. E. Hopcroft, and J. Wang, editors, Frontiers in Algorithmics - 8th International Workshop, FAW, volume 8497 of LNCS, pages 25–35. Springer, 2014.
H. Fernau, F. V. Fomin, D. Lokshtanov, M. Mnich, G. Philip, and S. Saurabh. Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology, 19(4):374–386, 2014.
M. Gobbert and H. Fernau. Latrunculi - on the complexity of Roman chess. In S. Bensch, R. Freund, and F. Otto, editors, Sixth Workshop on Non-Classical Models for Automata and Applications, NCMA, volume 304 of books@ocg.at, pages 115–130. Österreichische Computer Gesellschaft, 2014.
F. Beck, S. Gulan, B. Biegel, S. Baltes, and D. Weiskopf. RegViz: visual debugging of regular expressions. In P. Jalote, L. C. Briand, and A. van der Hoek, editors, 36th International Conference on Software Engineering, ICSE ’14, Companion Proceedings, pages 504–507. ACM, 2014.
2013
D. Binkele-Raible and H. Fernau. Packing paths: Recycling saves time. Discrete Applied Mathematics, 161(12):1686-1698, 2013.
D. Binkele-Raible, H. Fernau, S. Gaspers, and M. Liedloff. Exact and parameterized algorithms for Max Internal Spanning Tree. Algorithmica, 65:95-128, 2013.
J. Björklund, H. Fernau, and A. Kasprzik. MAT learning of universal automata. In A.-H. Dediu, C. Martín-Vide, and B. Truthe, editors, Language and Automata Theory and Applications, LATA , volume 7810 of LNCS , pages 141-152. Springer Berlin Heidelberg, 2013.
H. Fernau, R. Freund, S. Ivanov, M. L. Schmid, and K. G. Subramanian. Array insertion and deletion P systems. In G. Mauri, A. Dennunzio, L. Manzoni, and A. E. Porreca, editors, Unconventional Computation and Natural Computation 12th International Conference, UCNC , volume 7956 of LNCS , pages 67-78. Springer Berlin Heidelberg, 2013.
H. Fernau, P. Heggernes, and Y. Villanger. A multivariate analysis of some DFA problems. In A.-H. Dediu, C. Martín-Vide, and B. Truthe, editors, Language and Automata Theory and Applications, LATA , volume 7810 of LNCS , pages 275-286. Springer Berlin Heidelberg, 2013.
H. Fernau and M. L. Schmid. Pattern matching with variables: A multivariate complexity analysis (extended abstract). In J. Fischer and P. Sanders, editors, Combinatorial Pattern Matching, CPM , volume 7922 of LNCS , pages 83-94. Springer Berlin Heidelberg, 2013.
T. Ekim, P. Heggernes, and D. Meister. Polar permutation graphs are polynomial-time recognisable. European Journal of Combinatorics, 34(3):576-592, 2013.
A. Kasprzik. Four one-shot learners for regular tree languages and their polynomial characterizability. Theoretical Computer Science, 485C:85-106, 2013.
S. Gulan. Series parallel digraphs with loops - graphs encoded by regular expression. Theory of Computing Systems, 53(2):126-158, 2013.
D. Reidenbach and M. L. Schmid. Finding shuffle words that represent optimal scheduling of shared memory access. International Journal of Computer Mathematics, 90(6):1292-1309, 2013.
L. Brankovic and H. Fernau. A novel parameterised approximation algorithm for minimum vertex cover. Theoretical Computer Science, 511:85–108, 2013.
H. Fernau, M. L. Schmid, and Y. Villanger. On the parameterised complexity of string morphism problems. In A. Seth and N. K. Vishnoi, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), volume 24 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55-66. Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2013.
H. Fernau, M. L. Schmid, and K. G. Subramanian. Two-dimensional pattern languages. In S. Bensch, F. Drewes, R. Freund, and F. Otto, editors, Fifth Workshop on Non-Classical Models for Automata and Applications, NCMA, volume 294 of books@ocg.at, pages 117-132. Österreichische Computer Gesellschaft, 2013.
M. L. Schmid. Inside the class of REGEX languages. International Journal of Foundations of Computer Science, 24(7):1117–1134, 2013.
2012
G. Bai and H. Fernau. Constraint bipartite vertex cover: Simpler exact algorithms and implementations. Journal of Combinatorial Optimization, 23:331-355, 2012.
D. Binkele-Raible and H. Fernau. An exact exponential time algorithm for Power Dominating Set. Algorithmica, 63:323-346, 2012.
H. Fernau. Approximative learning vs. inductive learning. In N. M. Seel, editor, Encyclopedia of the Sciences of Learning, pages 293-295. Springer Berlin Heidelberg, 2012.
J. Chen, H. Fernau, P. Shaw, J. Wang, and Z. Yang. Kernels for packing and covering problems (extended abstract). In J. Snoeyink, P. Lu, K. Su, and L. Wang, editors, Sixth International Frontiers of Algorithmics Workshop FAW and Eighth International Conference on Algorithmic Aspects of Information and Management AAIM, volume 7285 of LNCS, pages 199-211. Springer Berlin Heidelberg, 2012.
T. Ekim, A. Erey, P. Heggernes, P. van 't Hof, and D. Meister. Computing minimum geodetic sets of proper interval graphs. In D. Fernández-Baca, editor, Theoretical Informatics - 10th Latin American Symposium, LATIN, volume 7256 of LNCS, pages 279-290. Springer Berlin Heidelberg, 2012.
P. Heggernes, D. Meister, and C. Papadopoulos. Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs. Discrete Applied Mathematics, 160(6):888-901, 2012.
L. Brankovic and H. Fernau. Parameterized approximation algorithms for Hitting Set. In R. Solis-Oba and G. Persiano, editors, Approximation and Online Algorithms: 9th International Workshop, WAOA 2011, volume 7164 of LNCS, pages 63–76. Springer Berlin Heidelberg, 2012.
D. Binkele-Raible and H. Fernau. Parameterized Measure & Conquer for Problems with No Small Kernels. Algorithmica, 64:189–212, 2012.
D. Binkele-Raible and H. Fernau. An exact exponential-time algorithm for the Directed Maximum Leaf Spanning Tree problem. Journal of Discrete Algorithms, 15:43–55, 2012.
H. Fernau. Cooperating Distributed Tree Automata. In: H. Bordihn, M. Kutrib and B. Truthe (editors): Dassow Festschrift, vol. 7300 of LNCS, pages 75–85. Springer Berlin Heidelberg, 2012.
D. Binkele-Raible, H. Fernau, F.V. Fomin, D. Lokshtanov, and S. Saurabh. Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Transactions on Algorithms, 8 (2012), paper no. 38.
C. Costa Florêncio and H. Fernau. On families of categorial grammars of bounded value, their learnability and related complexity questions. Theoretical Computer Science, 452: 21-38, 2012.
S. Bermudo and H. Fernau. Lower bounds on the differential of a graph", Discrete Mathematics, 312: 3236-3250, 2012.
2011
F. N. Abu-Khzam, H. Fernau, M. A. Langston, S. Lee-Cultura, and U. Stege. A fixed-parameter algorithm for string-to-string correction. Discrete Optimization, 8:41–49, 2011.
D. Binkele-Raible, L. Brankovic, M. Cygan, H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, M. Pilipczuk, P. Rossmanith, and J. O. Wojtaszczyk. Breaking the 2n -barrier for Irredundance: Two lines of attack. Journal of Discrete Algorithms, 9:214–230, 2011.
M. R. Fellows and H. Fernau. Facility location problems: A parameterized view. Discrete Applied Mathematics, 159:1118–1130, 2011.
H. Fernau, F. V. Fomin, D. Lokshtanov, M. Mnich, G. Philip, and S. Saurabh. Ranking and drawing in subexponential time. In C. S. Iliopoulos and W. F. Smyth, editors, Combinatorial Algorithms — 21st International Workshop, IWOCA 2010, volume 6460 of LNCS, pages 337–348. Springer, 2011.
S. Gulan. Graphs encoded by regular expressions. In T. Schwentick and C. Dürr, editors, 28th International Symposium on Theoretical Aspects of Computer Science, STACS, volume 9 of LIPIcs, pages 495–506. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2011.
H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, D. Raible, and P. Rossmanith. An exact algorithm for the Maximum Leaf Spanning Tree problem. Theoretical Computer Science, 412(45):6290-6302, 2011.
H. Fernau and R. Stiebe. On the expressive power of valences in cooperating distributed grammar systems. In J. Kelemen and A. Kelemenová, editors, Computation, Cooperation, and Life, volume 6610 of LNCS, pages 90-106. Springer Berlin Heidelberg, 2011.
B.-M. Bui-Xuan, P. Heggernes, D. Meister, and A. Proskurowski. A generic approach to decomposition algorithms, with an application to digraph decomposition. In B. Fu and D.-Z. Du, editors, Computing and Combinatorics COCOON, volume 6842 of LNCS, pages 331-342. Springer Berlin Heidelberg, 2011.
P. Golovach, P. Heggernes, D. Kratsch, D. Lokshtanov, D. Meister, and S. Saurabh. Bandwith on AT-free graphs. Theoretical Computer Science, 412:7001-7008, 2011.
P. Heggernes, D. Meister, and C. Papadopoulos. Graphs of linear clique-width at most 3. Theoretical Computer Science, 412(39):5466-5486, 2011.
P. Heggernes, D. Meister, and A. Proskurowski. Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs. Theoretical Computer Science, 412(12-14):1275-1297, 2011.
P. Heggernes, D. Meister, and U. Rotics. Computing the clique-width of large path powers in linear time via a new characterisation of clique-width. In A. S. Kulikov and N. K. Vereshchagin, editors, Computer Science Symposium in Russia CSR, volume 6651 o LNCS, pages 233-246. Springer Berlin Heidelberg, 2011.
A. Kasprzik. Inference of residual finite-state tree automata from membership queries and finite positive data. In G. Mauri and A. Leporati, editors, Developments in Language Theory DLT, volume 6795 of LNCS, pages 476-477. Springer Berlin Heidelberg, 2011.
A. Kasprzik and R. Yoshinaka. Distributional learning of simple context-free tree grammars. In J. Kivinen, C. Szepesvári, E. Ukkonen, and T. Zeugmann, editors, Algorithmic Learning Theory ALT, volume 6925 of LNCS, pages 398-412. Springer Berlin Heidelberg, 2011.
2010
D. Raible and H. Fernau. An Amortized Search Tree Analysis for k-Leaf Spanning Tree. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorn´y and B. Rumpe, editors, SOFSEM 2010: Theory and Practice of Computer Science, volume 5901 of LNCS, pages 672–684. Springer Berlin Heidelberg, 2010.
H. Fernau. A top-down approach to search-trees: improved algorithmics for 3-Hitting Set. Algorithmica, 57:97–18, 2010.
H. Fernau. Minimum Queens Dominating Set: a trivial programming exercise? Discrete Applied Mathematics, 158: 308–318, 2010.
F. N. Abu-Khzam, H. Fernau, M. A. Langston, S. Lee-Cultura and U. Stege. A Fixed-Parameter Algorithm for String-to-String Correction. Proceedings of the 16th Computing: the Australasian Theory Symposium (CATS 2010), volume 109 of Conferences in Research and Practices in Information Technology CRPIT, pages 31-37. Australian Computer Society ACS, 2010.
H. Fernau. Parameterized Algorithms for d-Hitting Set: the Weighted Case. Theoretical Computer Science, 411:1698-1713, 2010.
H. Fernau, M. Kaufmann, and M. Poths. Comparing trees via crossing minimization. Journal of Computer and System Sciences, 76:593–608, 2010.
C. Costa Florêncio and H. Fernau. Finding consistent categorial grammars of bounded value: a parameterized approach. In A. H. Dediu, H. Fernau, and C. Martín-Vide, editors. Language and Automata Theory and Applications LATA, volume 6031 of LNCS, pages 202-213. Springer Berlin Heidelberg, 2010.
H. Gruber and S. Gulan. Simplifying regular expressions: a quantitative perspective. In A. H. Dediu, H. Fernau, and C. Martín-Vide, editors. Language and Automata Theory and Applications LATA, volume 6031 of LNCS, pages 285-296. Springer Berlin Heidelberg, 2010.
A. Kasprzik and T. Kötzing. String extension learning using lattices. In A. H. Dediu, H. Fernau, and C. Martín-Vide, editors. Language and Automata Theory and Applications LATA, volume 6031 of LNCS, pages 380-391. Springer Berlin Heidelberg, 2010.
D. Binkele-Raible and H. Fernau. A faster exact algorithm for the directed maximum leaf spanning tree problem. In F. Ablayev and E. W. Mayr, editors, Computer Science in Russia CSR, volume 6072 of LNCS, pages 328-339. Springer Berlin Heidelberg, 2010.
D. Binkele-Raible, L. Brankovic, H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, and P. Rossmanith. A parameterized route to exact puzzles: Breaking the 2n-barrier for irredundance. In T. Calamoneri and J. Díaz, editors, Algorithms and Complexity CIAC, volume 6078 of LNCS, pages 311-322. Springer Berlin Heidelberg, 2010.
H. Fernau, F. V. Fomin, G. Philip, and S. Saurabh. The curse of connectivity: t-total vertex (edge) cover. In M. T. Thai and S. Sahni, editors, Computing and Combinatorics Conference COCOON, volume 6196 of LNCS, pages 34-43. Springer Berlin Heidelberg, 2010.
A. Kasprzik. Generalizing over several learning settings. In J. M. Sempere and P. García, editors, International Colloquium on Grammatical Inference ICGI, volume 6339 of LNCS, pages 288–202. Springer Berlin Heidelberg, 2010.
C. Costa Florêncio and H. Fernau. Hölder norms and a hierarchy theorem for parameterized classes of CCG. In J. M. Sempere and P. García, editors, International Colloquium on Grammatical Inference ICGI, volume 6339 of LNCS, pages 280–283. Springer Berlin Heidelberg, 2010.
D. Binkele-Raible and H. Fernau. A new upper bound for Max-2-SAT: A graph-theoretic approach. Journal of Discrete Algorithms, 8:388–401, 2010.
H. Fernau. Parameterized algorithmics for d-hitting set. International Journal of Computer Mathematics, 87(14):3157–3174, 2010.
D. Binkele-Raible, H. Fernau, S. Gaspers, and M. Liedloff. Exact exponential-time algorithms for finding bicliques. Information Processing Letters, 111(2):64–67, 2010.
L. Brankovic and H. Fernau. Combining two worlds: Parameterised approximation for vertex cover. In O. Cheong, K.-Y. Chwa, and K. Park, editors, Algorithms and Computation, 21st International Symposium, ISAAC 2010, Part I, volume 6506 of LNCS, pages 390-402. Springer Berlin Heidelberg, 2010.
Daniel Meister's publications of 2010 can be seen on his homepage.
2009
H. Fernau, J. A. Rodríguez, and J. M. Sigarreta. Offensive r-alliances in graphs. Discrete Applied Mathematics, 157:177-182, 2009.
A. Kasprzik. Making Finite-State Methods Applicable to Languages Beyond Context-Freeness via Multi-dimensional Trees. In: J. Piskorski, B. Watson, A. Yli-Jyrä (eds.) Post-proceedings of the 7th International Workshop on Finite-State Methods and Natural Language Processing, pp. 98-109. IOS Press, 2009.
A. Kasprzik. Two Equivalent Regularizations for Tree Adjoining Grammars. In: A. H. Dediu, A. M. Ionescu, C. Martin-Vide (eds.) LATA 2009, LNCS 5457, pp. 469-480. Springer Berlin Heidelberg (2009).
H. Fernau. Algorithms for learning regular expressions from positive data. Information and Computation, 207:521–541, 2009.
H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible, S. Saurabh and Y. Villanger. Kernel(s) for problems with no kernel: on out-trees with many leaves. In S. Albers and J.-Y. Marion, editors, Symposium on Theoretical Aspects of Computer Science STACS, pages 421–432. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Germany, 2009.
H. Fernau and D. Raible. Searching trees: an essay. In J. Chen and S. B. Cooper, editors, Theory and Applications of Models of Computation TAMC, volume 5532 of LNCS, pages 59–70. Springer Berlin Heidelberg, 2009.
H. Fernau and D. F. Manlove. Vertex and edge covers with clustering properties: Complexity and algorithms. Journal of Discrete Algorithms, 7:149–167, 2009.
J. M. Sigarreta, S. Bermudo, and H. Fernau. On the complement graph and defensive k-alliances. Discrete Applied Mathematics, 157:1687–1695, 2009.
H. Fernau and D. Raible. Packing paths: Recycling saves time. In S. Cafieri, A. Mucherino, G. Nannicini, F. Tarissan, and L. Liberti, editors, Cologne-Twente Workshop on Graphs and Combinatorial Optimization CTW, pages 79–83, 2009.
H. Fernau, S. Gaspers, D. Kratsch, M. Liedloff, and D. Raible. Exact exponential-time algorithms for finding bicliques in a graph. In S. Cafieri, A. Mucherino, G. Nannicini, F. Tarissan, and L. Liberti, editors, Cologne-Twente Workshop on Graphs and Combinatorial Optimization CTW, pages 205–209, 2009.
G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, D. Raible, and J. Rothe. The complexity of probabilistic lobbying. Technical Report abs/0906.4431, Arxiv, 2009. Conference version In F. Rossi und A. Tsouki`as (eds): International Conference on Algorithmic Decision Theory ADT, volume 5783 of LNCS, pages 86-97. Springer Berlin Heidelberg, 2009.
H. Fernau, S. Gaspers and D. Raible. Exact and parameterized algorithms for Max Internal Spanning Tree. In C. Paul and M. Habib, editors, Workshop on Graph-Theoretic Concepts in Computer Science WG, volume 5911 of LNCS, pages 100–111. Springer Berlin Heidelberg, 2009.
H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, D. Raible and P. Rossmanith. An exact algorithm for the Maximum Leaf Spanning Tree problem. In J. Chen and F. V. Fomin, editors, International Workshop on Parameterized and Exact Computations IWPEC, volume 5917 of LNCS, pages 161–172. Springer Berlin Heidelberg, 2009.
H. Fernau and D. Raible. A parameterized perspective on packing paths of length two. Journal of Combinatorial Optimization, 18:319–341, 2009.
2008
G. Bai and H. Fernau. Constraint bipartite vertex cover: Simpler exact algorithms and implementations. In F. P. Preparata, X. Wu, and J. Yin, editors, Frontiers in Algorithmics FAW, volume 5059 of LNCS, pages 67–78. Springer, 2008.
V. Dujmovic, H. Fernau, and M. Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited. Journal of Discrete Algorithms, 6:313–323, 2008.
M. R. Fellows and H. Fernau. Facility location problems: A parameterized view. In R. Fleischer and J. Xu, editors, Algorithmic Aspects in Information and Management AAIM 2008, volume 5034 of LNCS, pages 188–199. Springer, 2008.
H. Fernau. ROMAN DOMINATION: a parameterized perspective. International Journal of Computer Mathematics, 85:25–38, 2008.
H. Fernau and D. Raible. Exact algorithms for maximum acyclic subgraph on a superclass of cubic graphs. In S.-I. Nakano and Md. S. Rahman, editors, Workshop on Algorithms and Computation: WALCOM, volume 4921 of LNCS, pages 144–156. Springer, 2008. A long version is available as a Technical Report, Trierer Forschungsberichte; Informatik / Mathematik; No. 08-5, Univ. Trier, Germany.
H. Fernau, J. A. Rodríguez-Velázquez, and J. M. Sigarreta. Global r-alliances and total domination. In Proceedings of the 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pages 98–101. Universita degli Studi di Milano, 2008.
H. Fernau, J. F. Ryan, and K. A. Sugeng. A sum labelling for the generalised friendship graph. Discrete Mathematics, 308:734–740, 2008.
H. Fernau and R. Stiebe. Blind counter automata on ω-words. Fundamenta Informaticae, 83:51–64, 2008.
S. Gulan and H. Fernau. Local elimination-strategies in automata for shorter regular expressions. In Theory and Practice of Computer Science: SOFSEM 2008; volume II, pages 46–57. Institute of Computer Science, Faculty of Science, Pavol Jozef Safarik University, Kosice, Slovakia, 2008.
J. Chen, H. Fernau, D. Ning, D. Raible, and J. Wang. A parameterized perspective on P2-packings. Technical Report 0804.0570, ArXiv, http://arxiv.org/abs/0804.0570, 2008. Parts of this material is published at TAMC 08, parts of it at COCOA 08, see below.
H. Fernau. Parameterized algorithms for d-hitting set: the weighted case. Technical Report Trierer Forschungsberichte; Informatik / Mathematik; No. 08-6, Univ. Trier, Germany, July 2008.
D. Raible and H. Fernau. A new upper bound for MAX-2-SAT: A graph-theoretic approach. Technical Report 0803.3531, ArXiv, http://arxiv.org/abs/0803.3531, 2008. An extended abstract appeared in E. Ochmanski and J. Tyszkiewicz, editors, Mathematical Foundations of Computer Science MFCS, volume 5162 of LNCS, pages 551–562. Springer, 2008.
H. Fernau. Parameterized algorithms for drawing graphs. In M.-Y. Kao, ed., Encyclopedia of Algorithms, pp. 631–635. Springer, 2008.
H. Fernau and D. Raible. A parameterized perspective on packing paths of length two. In B. Yang, D.-Z. Du, and C. An Wang, editors, Combinatorial Optimization and Applications COCOA, volume 5165 of LNCS, pages 54–63. Springer, 2008.
S. Gulan and H. Fernau. Top-down construction of finite automata from regular expressions. Technical Report 08-7, Technical Reports Mathematics / Computer Science, University of Trier, Germany, http://www.uni-trier.de/fileadmin/fb4/INF/TechReports/Forschungsbericht 08-7.pdf, July 2008. Extended abstract to appear at the Proceedings of FSTTCS 2008.
Jiong Guo, Rolf Niedermeier, and Daniel Raible: Improved algorithms and complexity results for power domination in graphs. Algorithmica, 52(2):177–202, 2008.
J. Dassow and H. Fernau. Comparison of some descriptional complexities of 0L systems obtained by a unifying approach. Information and Computation, 206:1095–1103, 2008.
Daniel Raible and H. Fernau. Power Domination in O*(1.7548n) using Reference Search Trees. In S.-H. Hong, H. Nagamochi, and T. Fukunaga, editors, Proceedings of the 19th Symposium on Algorithms and Computation (ISAAC 2008), volume 5369 of LNCS, pages 136-147. Springer, 2008. The results were also presented at the Dagstuhl workshop on Exact and Parameterized Computation (Oct. 2008), as well as at the Graph Theory and Applications Workshop at the University of Newcastle, Australia (Dec. 2008).
F. N. Abu-Khzam, H. Fernau, and M. A. Langston. A bounded search tree algorithm for parameterized Face Cover. Journal of Discrete Algorithms, 6:541–552, 2008).
H. Fernau. Parameterized algorithmics for linear arrangement problems. Discrete Applied Mathematics, 156:3166-3177, 2008.
A. Kasprzik. A learning algorithm for multi-dimensional trees, or: Learning beyond context-freeness. In A. Clark, F. Coste, and L. Miclet, editors, Grammatical Inference: Algorithms and Applications ICGI, volume 5278 of LNCS, pages 111-124. Springer, 2008.
S. Gulan and H. Fernau. An optimal construction of finite automata from regular expressions. In R. Hariharan, M. Mukund, and V Vinay, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), Dagstuhl, Germany, 2008. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany.
C. Martin-Vide, F. Otto, and H. Fernau, editors. Languages and Automata Theory and Applications LATA, volume 5196 of LNCS. Springer, 2008.
2007
H. Fernau and D. Raible. Alliances in graphs: a complexity-theoretic study. In SOFSEM 2007, Proceedings Vol. II, pp. 61-70. Prague, Institute of Computer Science ASCR, 2007.
J. Dassow and H. Fernau. Comparison of some descriptional complexities of 0L systems obtained by a unifying approach. in Proceedings of the 1st International Conference on Language and Automata Theory and Applications LATA LATA 2007 , volume 35 of Technical Reports, pages 249–260. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, 2007 (Full version to appear in Information and Computation).
H. Fernau. Learning tree languages from text. RAIRO Informatique theorique/Theoretical Informatics and Applications, 41:351–374, 2007.
H. Fernau. Programmmed grammars with rule queues. International Journal of Foundations of Computer Science, 18:1209–1213, 2007.
H. Fernau, K. Reinhardt, and L. Staiger. Decidability of code properties. RAIRO Informatique theorique et Applications/Theoretical Informatics and Applications, 41:243–259, 2007.
J. Chen, H. Fernau, Y. A. Kanj, and G. Xia. Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM Journal on Computing, 37:1077–1108, 2007.
H. Fernau. Dynamic programming for Queen Domination. In J. L. Hurink, W. Kern, G. F. Post, and G. J. Still, editors, Proc. 6th Cologne-Twente Workshop on Graphs and Combinatorial Optimization CTW, pages 43–48. CTIT Centre for Telematics and Information Technology, Workshop Proceedings, 2007.
H. Fernau, J. A. Rodriguez, and J. M. Sigarreta. Offensive k-alliances in graphs. Technical Report 0703598, ArXiv, arxiv.org/abs/math.AG/0703598, 2007. Revised version accepted to Discrete Applied Mathematics.
D. Raible and H. Fernau. Exact elimination of cycles in graphs. In E. Demaine, G. Z. Gutin, D. Marx, and U. Stege, editors, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, number 07281 in Dagstuhl Seminar Proceedings, Dagstuhl, Germany, 2007. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.
H. Bordihn and H. Fernau. The degree of parallelism. Journal of Automata, Languages and Combinatorics, 12(1/2):25–47, 2007.
H. Fernau, R. Freund, M. Oswald, and K. Reinhardt. Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars. Journal of Automata, Languages and Combinatorics, 12(1/2):117–138, 2007.
2006
H. Fernau. ROMAN Domination: a parameterized perspective. In J. Stuller, J. Wiedermann, G. Tel, J. Pokorny and M. Bielikova (editors): Software Seminar SOFSEM 2006, vol. 3831 of LNCS, pp. 262-271. Berlin: © Springer, 2006.
F. Dehne, M. Fellows, H. Fernau, E. Prieto, and F. Rosamond. Nonblocker: parameterized algorithmics for Minimum Dominating Set. In J. Stuller, J. Wiedermann, G. Tel, J. Pokorny and M. Bielikova (editors): Software Seminar SOFSEM 2006, vol. 3831 of LNCS, pp. 237-245. Berlin: © Springer, 2006.
H. Fernau. Parameterized Algorithms for Hitting Set: the Weighted Case. In T. Calamoneri, I. Finocchi and G. F. Italiano (editors): CIAC 2006, vol. 3998 of LNCS, pp. 332-343. Berlin: © Springer, 2006. An extended version is available as a Technical Report from ECCC, TR06-072.
F. Abu Khzam and H. Fernau. Parameterized Algorithms for Finding Small Independent Dominating Sets in Planar Graphs. Electronic Notes in Discrete Mathematics, vol. 25, Special Issue on Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 1-6.
H. Fernau. Speeding up Exact Algorithms With High Probability. Electronic Notes in Discrete Mathematics, vol. 25, Special Issue on Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 57-59.
H. Fernau. Edge dominating set: efficient enumeration-based exact algorithms. In H. L. Bodlaender and M. Langston (editors) International Workshop on Parameterized and Exact Computation IWPEC 2006, vol. 4169 of LNCS, pp. 142-153. Berlin: © Springer, 2006.
F. Abu-Khzam and H. Fernau. Kernels: annotated, proper and induced. In H. L. Bodlaender and M. Langston (editors) International Workshop on Parameterized and Exact Computation IWPEC 2006, vol. 4169 of LNCS, pp. 264-275. Berlin: © Springer, 2006.
H. Fernau and D. F. Manlove. Vertex and edge covers with clustering properties: Complexity and algorithms. In Algorithms and Complexity in Durham ACiD 2006, pp. 69-84. © King's College, London, 2006. The report version (Univ. Glasgow) is electronically available .
H. Bordihn, H. Fernau, M. Holzer, V. Manca and C. Martin-Vide. Iterated Sequential Transducers as language generating devices. Theoretical Computer Science, vol. 369 (2006), pp. 67-81. An electronic copy may be obtained from the authors on request.
H. Fernau. Formal languages: 15th German meeting. Collection of open problems. Bulletin of the EATCS, vol. 90 (2006), pp. 232-236.
2005
H. Fernau. Two-layer planarization: improving on parameterized algorithmics. In P. Vojtas et. al. (editors): SOFSEM 2005: Theory and Practice of Computer Science, vol. 3381 of LNCS, pp. 137-146. Berlin: © Springer, 2005.
J. Chen, H. Fernau, I.A. Kanj and G. Xia. Parametric duality and kernelization: lower bounds and upper bounds on kernel size. In V. Diekert and B. Durand (editors): Symposium on Theoretical Aspects of Computer Science STACS 2005, vol. 3404 of LNCS, pp. 269-280. Berlin: © Springer, 2005.
H. Fernau, R. Freund and M. Holzer. Representations of recursively enumerable array languages by contextual array grammars. Fundamenta Informaticae, vol. 64 (2005), pp. 159-170.
F. N. Abu-Khzam and H. Fernau and M. A. Langston. Asymptotically faster algorithms for parameterized FACE COVER. In: Algorithms and Complexity in Durham ACiD 2005 , Texts in Algorithmics series of KCL publications. Also available as Technical Report of the University of Tennessee, USA, Computer Science, No. ut-cs-05-564.
H. Bordihn and H. Fernau. The degree of parallelism. In C.~Mereghetti, B.~Palano, G.~Pighizzini and D.~Wotschke (editors): Descriptional Complexity of Formal Systems 7th Workshop DCFS 2005. Universita di Milano, Dipartimento di Informatica e Comunicazione, Rapporto Tecnico 06-05, pp. 51-62, 2005.
H. Fernau, R. Freund, M. Oswald and K. Reinhardt. Refining the nonterminal complexity of graph-controlled grammars. In C.~Mereghetti, B.~Palano, G.~Pighizzini and D.~Wotschke (editors): Descriptional Complexity of Formal Systems 7th Workshop DCFS 2005. Universita di Milano, Dipartimento di Informatica e Comunicazione, Rapporto Tecnico 06-05, pp. 110-121, 2005.
L. Brankovic and H. Fernau. Approximability of a {0,1}-matrix problem. In P. Manyem, M. Miller and J. Ryan (editors): 16th Australasian Workshop on Combinatorial Algorithms AWOCA 2005. 2005.
H. Fernau. Algorithms for learning regular expressions. In S. Jain, H.-U. Simon and E. Tomita (editors): Algorithmic Learning Theory ALT 2005, vol. 3734 of LNCS/LNAI, pp. 297-311. Berlin: © Springer, 2005. (Springer somehow confused some pictures in the production process, so above you can find the original submitted version.)
J. Alber, H. Fan, M. R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, and U. Stege. A refined search tree techniques for PLANAR DOMINATING SET on planar graphs. Journal of Computer and System Sciences, vol. 71 (2005), pp. 385-405.
H. Fernau. Two-layer planarization: improving on parameterized algorithmics. Journal of Graph Algorithms and Applications, vol. 9 (2005), pp. 205-238.
H. Fernau, M. Kaufmann and M. Poths. Comparing trees via crossing minimization. In R. Ramanujam and Sandeep Sen (editors): Foundations of Software Technology and Theoretical Computer Science FSTTCS 2005, vol. 3821 of LNCS, pp. 457-469. Berlin: © Springer, 2005.
J.
Guo, R.
Niedermeier, and Daniel Raible. Improved
algorithms and complexity results for power domination in graphs.
In
Proceedings
of the 15th International Symposium on Fundamentals of Computation
Theory (FCT'05),
Lübeck, Germany. August 2005.
Volume 3623 in Lecture Notes in
Computer Science, pages 172–184, Springer (original
publication).
2004
H. Fernau. Parallel grammars: a short phenomenology. In C. Martin-Vide, V. Mitrana and Gh. Paun (editors): Formal Languages and Applications. pp. 175-182. Heidelberg: © Springer-Verlag, 2004. Vol. 148 in the Studies in Fuzziness and Soft Computing series.
H. Fernau. Identifying terminal distinguishable languages. Annals of Mathematics and Artificial Intelligence, vol. 40 (2004), pp. 263-281.
H. Fernau. Complexity of a {0,1}-matrix problem. The Australasian Journal of Combinatorics, vol. 29 (2004), pp. 273-300.
J. Alber, H. Fernau and R. Niedermeier. Parameterized complexity: exponential speedup for planar graph problems. Journal of Algorithms, vol. 52 (2004), pp. 26-56.
H. Fernau and C. de la Higuera. Grammar induction: an invitation for formal language theorists. GRAMMARS, vol. 7 (2004), pp. 45-55.
H. Fernau and D. Juedes. A geometric approach to parameterized algorithms for domination problems on planar graphs. In J. Fiala et al. (editors): Mathematical Foundations of Computer Science MFCS 2004, vol. 3153 of LNCS, pp. 488-499. Berlin: © Springer-Verlag, 2004.
H. Fernau. Extracting minimum length Document Type Definitions is NP-hard (Abstract) In G. Paliouras and Y. Sakakibara (editors): International Colloquium on Grammatical Inference ICGI 2004, vol. 3264 of LNCS/LNAI, pp. 277-278. Berlin: © Springer-Verlag, 2004.
B. Starkie and H. Fernau. The Boisdale Algorithm - an induction method for a subclass of unification grammar from positive data. In G. Paliouras and Y. Sakakibara (editors): International Colloquium on Grammatical Inference ICGI 2004, vol. 3264 of LNCS/LNAI, pp. 235-247. Berlin: © Springer-Verlag, 2004. The test examples can be obtained from the authors on request.
2003
H. Fernau. Identification of function distinguishable languages. Theoretical Computer Science, vol. 290 (2003), pp. 1679-1711.
H. Fernau and A. Meduna. On the degree of scattered context-sensitivity. Theoretical Computer Science, vol. 290 (2003), pp. 2121-2124.
H. Bordihn, H. Fernau and M. Holzer. On iterated sequential transducers. In C. Martin-Vide and V. Mitrana (editors): Grammars and Automata for String Processing: from Mathematics and Computer Science to Biology, and Back. London: Taylor and Francis, 2003, pp. 121-130.
H. Fernau. Nonterminal complexity of programmed grammars. Theoretical Computer Science, vol. 296 (2003), pp. 225-251.
H. Fernau, R. Freund and M. Holzer. Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes < k and = k. Theoretical Computer Science, vol. 299 (2003), pp. 633-662.
H. Fernau and A. Meduna. A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. Information Processing Letters, vol. 86 (2003), pp. 235-240.
H. Fernau. Parallel grammars: a phenomenology. Preprint version. GRAMMARS, vol. 6 (2003), pp. 25-87.
H. Fernau, T. Hagerup, N. Nishimura, P. Ragde, and K. Reinhardt. On the parameterized complexity of a generalized Rush Hour puzzle. In: Canadian Conference on Computational Geometry CCCG'03, pp. 6-9. The results were also presented at the Dagstuhl workshop on Parameterized Complexity in 2003.
H. Fernau. Education(al) matters: teaching P versus NP. EATCS Bulletin, vol. 80 (2003), pp. 237-246.
J. Alber, H. Fernau and R. Niedermeier. Graph separators: a parameterized view. Journal of Computer and System Sciences, vol. 67 (2003), pp. 808-832.
V. Dujmovic, H. Fernau and M. Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited. In G. Liotta (editor): Graph Drawing GD 2003. vol. 2912 of LNCS, pp. 332-344. Berlin: © Springer-Verlag, 2004. The results were also presented at the Dagstuhl workshop on Parameterized Complexity in 2003.
2002
H. Fernau and R. Stiebe. Valuated and valence grammars: an algebraic view. IN: W. Kuich and G. Rozenberg (ed.), Proceedings DLT 2001, © Springer-Verlag, LNCS 2295, pages 281-292, 2002.
H. Fernau and R. Stiebe. Sequential grammars and automata with valences. Theoretical Computer Science, vol. 276 (2002), pp. 377-405.
H. Bordihn, H. Fernau and M. Holzer. Accepting pure grammars. Publicationes Mathematicae, Debrecen, vol. 60 Supplement (2002), pp. 483-510.
J. Alber, H.L. Bodlaender, H. Fernau, T. Kloks and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, vol. 33 (2002), pp. 461-493.
H. Fernau. Learning tree languages from text. In J. Kivinen and R.H. Sloan (editors): Computational Learning Theory COLT 2002, vol. 2375 of LNCS/LNAI, pp. 153-168. Berlin: © Springer-Verlag, 2002.
H. Fernau and A. Radl. Algorithms for learning function distinguishable regular languages. In T. Caelli, A. Amin, R.P.W. Duin, M. Kamel and D. de Ridder (editors): Structural, Syntactic, and Statistical Pattern Recognition SSPR and SPR 2002, vol. 2396 of LNCS, pp. 64-72. Berlin: © Springer-Verlag, 2002.
H. Fernau. On parameterized enumeration. In O.H. Ibarra and L. Zhang (editors): Computing and Combinatorics, Proceedings COCOON 2002, vol. 2383 of LNCS, pp. 564-573. Berlin: © Springer-Verlag, 2002.
H. Fernau. Fragmentation: enhancing identifiability. In P. Adriaans, H. Fernau and M. van Zaanen (editors): Grammatical Inference: Algorithms and Applications; 6th International Colloquium: ICGI 2002, vol. 2484 of LNCS/LNAI, pp. 92-105. Berlin: © Springer-Verlag, 2002.
H. Fernau. Graph separator algorithms: a refined analysis. In L. Kucera (editor): Graph-Theoretic Concepts in Computer Science WG 2002. vol. 2573 of LNCS, pp. 186-197. Berlin: © Springer-Verlag, 2002.
H. Fernau. Even linear simple matrix languages: formal language properties and grammatical inference. Theoretical Computer Science, vol. 289 (2002), pp. 425-456.
H. Fernau and M. Holzer. Graph controlled cooperating distributed grammar systems with singleton components. Journal of Automata, Languages, and Combinatorics, vol. 7 (2002), pp. 487-503.