Research Activity -
Algorithms and Complexity

Haiko Müller

Haiko Müller's Papers

• "On stable cutsets in claw-free graphs and planar graphs"
  Van Bang Le, Raffaele Mosca and Haiko Müller
  short version Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Springer-Verlag, Lecture Notes in Computer Science 3787, pages 163-174, 2005.
  


• "Computing the branchwidth of interval graphs"
  Ton Kloks, Jan Kratochvíl and Haiko Müller
  full version Discrete Applied Mathematics 145, pages 266-275, 2005.
  short version Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS'99), Springer-Verlag, Lecture Notes in Computer Science 1563, pages 173-183, 1999.
  


• "On treewidth approximations"
  Vincent Bouchitté, Dieter Kratsch, Haiko Müller and Ioan Todinca
  full version Discrete Applied Mathematics 136, pages 183-196, 2004.
  short version Proceedings of the 1st CologneTwente Workshop on Graphs and Combinatorial Optimization 2001.
  


• "Algorithms for graphs with small octopus"
  Fedor V. Fomin, Dieter Kratsch and Haiko Müller
  full version Discrete Applied Mathematics 134, pages 105-128, 2004.
  short version University of Leeds, School of Computing Research Report Series No. 2001.12, Leeds 2001.
  


• "On the Recognition of General Partition Graphs"
  Ton Kloks, Chuan-Min Lee, Jiping Liu and Haiko Müller
  short version Lecture Notes in Computer Science 2880, pages 273-283, 2003.
  


• "Feedback Vertex Set and Longest Induced Path on AT-Free Graphs"
  Dieter Kratsch, Haiko Müller and Ioan Todinca
  short version Lecture Notes in Computer Science 2880, pages 309-321, 2003.
  


• "Splitting a graph into disjoint induced paths or cycles"
  Hoàng-Oanh Le, Van Bang Le and Haiko Müller
  full version Discrete Applied Mathematics 131, Issue 1 pages 199-212, 2003.
  


• "Additive tree spanners"
  Dieter Kratsch, Hoàng-Oanh Le, Haiko Müller, Erich Prisner and Dorothea Wagner,
  full version SIAM Journal on Discrete Mathematics 17, pages 332-340, 2003.
  


• "On the domination search number"
  Fedor V. Fomin, Dieter Kratsch and Haiko Müller
  full version Discrete Applied Mathematics 127, Issue 3 pages 565-580, 2003.
  short version Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), Springer-Verlag, Lecture Notes in Computer Science 1928, pages 161-171, 2000.
  


• "Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources"
  Mary Cryan, Martin Dyer, Haiko Müller and Leen Stougie
  short version Proceedings of the 14th Annual Symposium on Discrete Algorithms (SODA 03), pages 330-339, 2003.


• "A generalization of AT-free graphs and a generic algorithm for solving triangulation problems"
  Hajo Broersma, Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Algorithmica 32, pages 594-610, 2002.
  short version Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'98), Springer-Verlag, Lecture Notes in Computer Science 1517, pages 88-99, 1998.
  


• "On the structure of graphs with bounded asteroidal number"
  Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Graphs and Combinatorics 17, pages 295-306, 2001.
  short version Proceedings of the 6th Twente Workshop on Graphs and Combinatorial Optimization 1999.
  


• "Efficient algorithms for graphs with few P₄'s"
  Luitpold Babel, Ton Kloks, Jan Kratochvíl, Dieter Kratsch, Haiko Müller and Stephan Olariu
  full version Discrete Mathematics 235, pages 29-51, 2001.
  


• "On the tree-degree of graphs"
  Maw-Shang Chang and Haiko Müller
  short version Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Springer-Verlag, Lecture Notes in Computer Science 2204, pages 44-54, 2001.
  


• "Partial orders on weak orders convex subsets"
  Haiko Müller and Jean-Xavier Rampon
  full version Order 17 pages 103-123, 2000.
  


• "Finding and counting small subgraphs efficiently"
  Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Information Processing Letters 74, pages 115-121, 2000.
  short version Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'95), Springer-Verlag, Lecture Notes in Computer Science 1017, pages 14-23, 1995.
  


• "Degree-preserving trees"
  Hajo Broersma, Andreas Huck, Ton Kloks, Otto Koppius, Dieter Kratsch, Haiko Müller and Hilde Tuinstra
  full version Networks 35, pages 26-39, 2000.
  short version Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS'98), Springer-Verlag, Lecture Notes in Computer Science 1450, pages 713-721, 1998.
  


• "Bandwidth of split and circular permutation graphs"
  Ton Kloks, Dieter Kratsch, Yvan Le Borgne and Haiko Müller
  short version Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), Springer-Verlag, Lecture Notes in Computer Science 1928, pages 243-254, 2000.
  


• "On the vertex ranking problem for trapezoid, circular-arc and other graphs"
  Jitender S. Deogun, Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Discrete Applied Mathematics 98, pages 39-63, 1999.
  short version Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science (STACS'94), Springer-Verlag, Lecture Notes in Computer Science 775, pages 747-758, 1994.
  


• "Approximating the bandwidth for asteroidal triple-free graphs"
  Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Journal of Algorithms 32, pages 41-57, 1999.
  short version Proceedings of the 3rd Annual European Symposium on Algorithms (ESA'95), Springer-Verlag, Lecture Notes in Computer Science 979, pages 434-447, 1995.
  


• "Independent sets in asteroidal triple-free graphs"
  Hajo Broersma, Ton Kloks, Dieter Kratsch and Haiko Müller
  full version SIAM Journal on Discrete Mathematics 12, pages 276-287, 1999.
  short version Proceedings of the 24th International Colloquium on Automata, Languages, and Programming (ICALP'97), Springer-Verlag, Lecture Notes in Computer Science 1256, pages 760-770, 1997.
  


• "Bandwidth on chain graphs"
  Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Information Processing Letters 68, pages 313-315, 1998.
  


• "Vertex ranking of asteroidal triple-free graphs"
  Ton Kloks, Haiko Müller and C. K. Wong
  full version Information Processing Letters 68, pages 201-206, 1998.
  short version Proceedings of the 7th Annunal International Symposium on Algorithms and Computation (ISAAC'96), Springer-Verlag, Lecture Notes in Computer Science 1178, pages 174-182, 1996.
  


• "Treewidth and minimum fill-in on d-trapezoid graphs"
  Hans L. Bodlaender, Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Journal of Graph Algorithms and Applications 2, pages 1-23, 1998.
  


• "Ranking of graphs"
  Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller and Zsolt Tuza
  full version SIAM Journal on Discrete Mathematics 11, pages 168-181, 1998.
  short version 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'94), Springer-Verlag, Lecture Notes in Computer Science 903, pages 292-304, 1995.
  


• "Recognizing interval digraphs and interval bigraphs in polynomial time"
  Haiko Müller
  full version Discrete Applied Mathematics 78, pages 189-205, 1997.


• "Measuring the vulnerability for classes of intersection graphs"
  Ton Kloks, Dieter Kratsch and Haiko Müller
  full version Discrete Applied Mathematics, 77, pages 259-270, 1997.
  


• "Partial orders and their convex subsets"
  Jean-Xavier Rampon and Haiko Müller
  full version Discrete Mathematics 165/166, pages 507-517, 1997.
  


• "HAMILTONian circuits in chordal bipartite graphs"
  Haiko Müller
  full version Discrete Mathematics 156, pages 291-298, 1996.
  


• "Toughness, hamiltonicity and spit graphs"
  Dieter Kratsch, Jenö Lehel and Haiko Müller
  full version Discrete Mathematics 150, pages 231-245, 1996.
  


• "On edge perfectness and classes of bipartite graphs"
  Haiko Müller
  full version Discrete Mathematics 149, pages 159-187, 1996.
  


• "The minimum broadcast time problem for several processor networks"
  Klaus Jansen and Haiko Müller
  full version Theoretical Computer Science 147, pages 69-85, 1995.
  short version Proceedings of the 1st Canada-France Conference on Parallel and Distributed Computing, Springer-Verlag, Lecture Notes in Computer Science 805, pages 219-234, 1994.
  


• "Dominoes"
  Ton Kloks, Dieter Kratsch and Haiko Müller
  short version Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'94) Springer-Verlag, Lecture Notes in Computer Science 903, pages 106-120, 1995.
  


• "Computing TREEWIDTH and MINIMUM FILL-IN: all you need are all minimal separators"
  Ton Kloks, Hans L. Bodlaender, Dieter Kratsch and Haiko Müller
  short version Proceedings of the First Annual European Symposium on Algorithms (ESA'93), Springer-Verlag, Lecture Notes in Computer Science 726, pages 260-271, 1993.
  


• "Polynomial time algorithms for HAMILTONian problems on bipartite distance hereditary graphs"
  Haiko Müller and Falk Nicolai
  full version Information Processing Letters 46, pages 225-230, 1993.
  


• "A note on balanced immunity"
  Haiko Müller
  full version Mathematical Systems Theory 26, pages 157-167, 1993.
  


• "Domination in convex and chordal bipartite graphs"
  Peter Damaschke, Dieter Kratsch and Haiko Müller
  full version Information Processing Letters 36, pages 231-236, 1990.
  


• "Alternating cycle-free matchings"
  Haiko Müller
  full version Order 7, pages 11-21, 1990.
  


• "The NP-completeness of STEINER TREE and DOMINATING SET for chordal bipartite graphs"
  Andreas Brandstädt and Haiko Müller
  full version Theoretical Computer Science 53, pages 257-265, 1987.