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.
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 D. 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), vol. 3623 of LNCS, pp. 172–184. Berlin: © Springer, 2005. (original publication).