Universität Rostock |  Fakultät für Informatik und Elektrotechnik |  Institut für Informatik |  Wissenschaftsbereich Theoretische Informatik   

Selected Publications

My current h-index is 18, and my g-index is 37 (if my name is spelled Andreas Brandstadt; various other spellings give different results and cover some of my other papers which are not covered by the previous spelling).

Papers in Refereed Journals:

  1. Independent Sets of Maximum Weight in Apple-Free Graphs, (with V.V. Lozin and R. Mosca), accepted for SIAM J. Discrete Math.
  2. Rooted directed path graphs are leaf powers, (with Ch. Hundt, F. Mancini, and P. Wagner), Discrete Mathematics 310 (2010) 897-910
  3. Characterising (k,l)-leaf powers, (with P. Wagner), Discrete Applied Mathematics 158 (2010) 110-122
  4. The complete inclusion structure of leaf power classes, (with P. Wagner), Theoretical Computer Science 410 (2009) 5505-5514
  5. Simplicial powers of graphs, (with V.B. Le), Theoretical Computer Science 410 (2009) 5443-5454
  6. A Forbidden Induced Subgraph Characterization of Distance-Hereditary 5-Leaf Powers, (with V.B. Le and D. Rautenbach), Discrete Mathematics 309 (2009) 3843-3852
  7. Structure and Linear Time Recognition of 4-Leaf Powers, (with V.B. Le and R. Sritharan), electronically available in ACM Transactions on Algorithms vol. 5, 1 (2008)
  8. On independent vertex sets in subclasses of apple-free graphs, (with T. Klembt, V.V. Lozin and R. Mosca), Algorithmica 56 (2010) 383-393
  9. Maximum induced matching for chordal graphs in linear time, (with Chinh T. Hoàng), Algorithmica 52, no. 4 (2008) 440-447
  10. Tree spanners for bipartite graphs and probe interval graphs, (with F.F. Dragan, H.-O. Le, V.B. Le and R. Uehara), Algorithmica 47, no. 1 (2007) 27-51
  11. On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set problem, (with Chinh T. Hoàng), Theoretical Computer Science 389 (2007) 295-306
  12. The induced matching and chain subgraph cover problems for convex bipartite graphs, (with Elaine M. Eschen and R. Sritharan), Theoretical Computer Science 381 (1-3) (2007) 260-265
  13. New applications of the clique separator decomposition for the Maximum Weight Stable Set problem, (with V.B. Le and S. Mahfud), Theoretical Computer Science 370 (2007) 229-239
  14. Structure and linear time recognition of 3-leaf powers, (with V.B. Le), Information Processing Letters 98 (2006) 133-138
  15. P6- and triangle-free graphs revisited: Structure and bounded clique-width, (with T. Klembt and S. Mahfud), Discrete Mathematics and Theoretical Computer Science 8 (2006) 173-188
  16. Clique-width for four-vertex forbidden subgraphs, (with J. Engelfriet, H.-O. Le, and V.V. Lozin), Theory of Computing Systems 39 (2006) 561-590
  17. On algorithms for (P5,gem)-free graphs, (with Hans L. Bodlaender, Dieter Kratsch, Michael Rao and Jeremy Spinrad), Theoretical Computer Science 349 (2005) 2-21
  18. Bisplit graphs (with P.L. Hammer, V.B. Le and V.V. Lozin), Discrete Mathematics 299 (2005) 11-32
  19. New graph classes of bounded clique-width, (with F.F. Dragan, H.-O. Le and R. Mosca), Theory of Computing Systems 38 (2005) 623-645
  20. On the structure of (P5,gem)-free graphs, (with D. Kratsch), Discrete Applied Mathematics 145 (2005) 155-166
  21. Chordal co-gem-free graphs and (P5,gem)-free graphs have bounded clique-width, (with H.-O. Le and R. Mosca), Discrete Applied Mathematics 145 (2005) 232-241
  22. On minimal prime extensions of a four-vertex graph in a prime graph, (with Chinh T. Hoàng and J.-M. Vanherpe ), Discrete Mathematics 288 (2004) 9-17
  23. Gem- and co-gem-free graphs have bounded clique-width, (with H.-O. Le, and R. Mosca), Internat. J. of Foundations of Computer Science 15 (2004) 163-185
  24. (P5,Diamond)-Free Graphs Revisited: Structure and Linear Time Optimization, Discrete Applied Mathematics 138 (2004) 13-27
  25. Efficient robust algorithms for the Maximum Weight Stable Set problem in chair-free graph classes (with V.B. Le and H.N. de Ridder), Information Processing Letters 89 (2004) 165-173
  26. Split-Perfect Graphs: Characterizations and Algorithmic Use (with V.B. Le), SIAM J. Discrete Math. 17 (2004) 341-360
  27. Tree spanners on chordal graphs: complexity and algorithms, (with F.F. Dragan,, H.-O. Le and V.B. Le), Theoretical Computer Science 310 (2004) 329-354
  28. On the Structure and Stability Number of P5- and Co-Chair-Free Graphs, (with R. Mosca), Discrete Applied Mathematics 132 (2004) 47-65
  29. Stability Number of Bull- and Chair-Free Graphs Revisited, (with Chinh T. Hoàng and V.B. Le), Discrete Applied Mathematics 131 (2003) 39-50
  30. On linear and circular structure of (claw,net)-free graphs, (with F.F. Dragan), Discrete Applied Mathematics 129 (2003) 285-303
  31. On variations of P4-sparse graphs, (with R. Mosca), Discrete Applied Mathematics 129 (2003) 521-532
  32. On the linear structure and clique width of bipartite permutation graphs, (with V.V. Lozin), Ars Combinatoria Vol. LXVII (2003) 273-281
  33. Structure and stability number of chair-, co-P-, and gem-free graphs revisited, (with H.-O. Le, and J.-M. Vanherpe), Information Processing Letters 86 (2003) 161-167
  34. Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time, (with S. Mahfud), Information Processing Letters 84 (2002) 251-259
  35. Recognizing the P4-structure of claw-free graphs and a larger graph class, (with L. Babel and V.B. Le), Discrete Math. and Theor. Computer Science 5 (2002) 127-146
  36. On alpha-redundant vertices in P5-free graphs (with H.-O. Le and V.B. Le), Information Processing Letters 82 (2002) 119-122
  37. A note on alpha-redundant vertices in graphs (with V.V. Lozin), Discrete Applied Mathematics 108 (2001) 301-308
  38. Linear time algorithms for Hamiltonian problems on (claw,net)-free graphs (with F.F. Dragan and E. Köhler), SIAM J. Computing 30 (2000) 1662-1677
  39. Efficiently Recognizing the P4-structure of Trees and of Bipartite Graphs Without Short Cycles (with V.B. Le and S. Olariu), Graphs and Combinatorics 16 (2000) 381-387
  40. On stable cutsets in graphs (with F.F. Dragan, V.B. Le and T. Szymczak), Discrete Applied Mathematics 105 (2000) 39-50
  41. Recognizing the P4-structure of block graphs (with V.B. Le), Discrete Applied Mathematics 99 (2000) 349-366
  42. Distance approximating trees for chordal and dually chordal graphs (with V.D. Chepoi and F.F. Dragan), J. Algorithms 30 (1999) 166-184
  43. Tree- and Forest-Perfect Graphs (with V.B. Le), Discrete Applied Mathematics 95 (1999) 141-162
  44. On the stability number of claw-free P5-free and more general graphs (with P.L. Hammer), Discrete Applied Mathematics 95 (1999) 163-167
  45. Recognizing the P4-structure of bipartite graphs (with L. Babel and V.B. Le), Discrete Applied Mathematics 93 (1999) 157-168
  46. Convexity and HHD-free graphs (with F.F. Dragan and F. Nicolai), SIAM J. Discrete Math. 12 (1999) 119-135
  47. The complexity of some problems related to graph 3-colorability (with V.B. Le and T. Szymczak), Discrete Applied Mathematics 89 (1998) 59-73
  48. A Linear-Time Algorithm for Connected r-Domination and Steiner Tree on Distance-Hereditary Graphs (with F.F. Dragan), Networks 31 (1998) 177-182
  49. The algorithmic use of hypertree structure and maximum neighbourhood orderings (with V.D. Chepoi and F.F. Dragan), Discrete Applied Mathematics 82 (1998) 43-77
  50. Dually chordal graphs (with F.F. Dragan, V.D. Chepoi and V.I. Voloshin), SIAM J. Discrete Math. 11 (1998) 437-455
  51. Powers of HHD-free graphs (with F.F. Dragan and F. Nicolai), Internat. Journal of Computer Mathematics 69 (1998) 217-242
  52. Duchet-Type Theorems for powers of HHD-free graphs (with V.B. Le and T. Szymzcak), Discrete Mathematics 177 (1997) 9-16
  53. LexBFS-orderings and powers of chordal graphs (with F.F. Dragan and F. Nicolai), Discrete Mathematics 171 (1997) 27-42
  54. Homogeneously orderable graphs (with F.F. Dragan and F. Nicolai), Theoretical Computer Science 172 (1997) 209-232
  55. Clique r-domination and clique r-packing problems on dually chordal graphs (with V.D. Chepoi and F.F. Dragan), SIAM J. Discrete Math. 10 (1997) 109-127
  56. r-Dominating cliques in graphs with hypertree structure (with F.F. Dragan), Discrete Mathematics 162 (1996) 93-108
  57. Perfect elimination orderings of chordal powers of graphs (with V.D. Chepoi and F.F. Dragan), Discrete Mathematics 158 (1996) 273-278
  58. Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics 152 (1996) 47-54; Corrigendum: Discrete Mathematics 186 (1998) 295
  59. Short disjoint cycles in graphs with degree constraints (with H.-J. Voss), Discrete Applied Mathematics 64 (1996) 197-205
  60. Classes of bipartite graphs related to chordal graphs, Discrete Applied Mathematics 32 (1991), 51-60
  61. Bipartite permutation graphs (with J.P. Spinrad and L.K. Stewart), Discrete Applied Mathematics 18 (1987) 279-292
  62. On domination problems for permutation and other graphs (with D. Kratsch), Theoretical Computer Science 54 (1987) 181-198
  63. The NP-completeness of STEINER TREE and DOMINATING SET for chordal bipartite graphs (with H. Müller), Theoretical Computer Science 53 (1987) 257-265
  64. Uniform simulations of nondeterministic real time multitape Turing machines, (with F.J. Brandenburg and K.W. Wagner), Math. Systems Theory 19 (1987) 277-299
  65. The computational complexity of Feedback Vertex Set, Hamiltonian Circuit, Dominating Set, Steiner Tree and Bandwidth on Special Perfect Graphs, Journal of Information Processing and Cybern. (EIK) 23, 8/9 (1987) 471-477
  66. Bipartite permutation graphs are bipartite tolerance graphs (with J.P. Spinrad and L.K. Stewart), Congressus Numerantium 58 (1987) 165-174
  67. On partitions of permutations into increasing and decreasing subsequences (with D. Kratsch) Elektron. Informationsverarb. u. Kybernetik 22 (1986) 5/6, 263-273
  68. Space classes, intersections of languages and bounded erasing homomorphisms, R.A.I.R.O. Informatique Theorique 17 (1983) 121-130
  69. Closure properties of certain families of formal languages with respect to a generalization of cyclic closure, R.A.I.R.O. Informatique Theorique 15 (1981) 233-252
  70. A relation between space, return and dual return complexities (with G. Wechsung), Theoretical Computer Science 9 (1979) 127-140
  71. On a property of homogeneous Gaussian L-fields (in Russian), Probability Theory and its Applications 3 (1979), 596-600 (Teorija werojatnostjej i jejo primenenija)
  72. On a family of complexity measures on Turing machines defined by predicates, Elektron. Inf.verarb. u. Kybern. 14 (1978) 11, 331-339
  73. Eine Hierarchie beschränkter Rückkehrberechnungen auf online Turingmaschinen (with D. Saalfeld), Elektron. Inf.verarb. u. Kybern. 13 (1977) 11, 571-583

Papers (Extended Abstracts) in Refereed Conference Proceedings:

  1. Efficient Edge Domination on Hole-free Graphs in Polynomial Time, (with C. Hundt and R. Nevries), extended abstract accepted for: Proceedings LATIN 2010, Oaxaca, Mexico 2010, LNCS
  2. Path-Bicolorable Graphs, (with M.C. Golumbic, V.B. Le, and M. Lipshteyn), extended abstract to appear in: Proceedings of ``Graph Theory, Computational Intelligence and Thought - A Conference Celebrating Martin C. Golumbic's 60th Birthday'', Israel 2008, Lecture Notes in Computer Science 5420, 172-182
  3. On Distance-3 Matchings and Induced Matchings, (with R. Mosca), extended abstract to appear in: Proceedings of ``Graph Theory, Computational Intelligence and Thought - A Conference Celebrating Martin C. Golumbic's 60th Birthday'', Israel 2008, Lecture Notes in Computer Science 5420, 116-126
  4. Independent Sets of Maximum Weight in Apple-Free Graphs, (with T. Klembt, V.V. Lozin and R. Mosca), extended abstract in: Proceedings ISAAC 2008, Gold Coast, Australia, 2008, Lecture Notes in Computer Science 5369, 848-858
  5. Simplicial powers of graphs, (with V.B. Le), extended abstract in: Proceedings COCOA 2008, St. John's, Newfoundland, 2008, Lecture Notes in Computer Science 5165, 160-170
  6. On k- versus (k+1)-leaf powers, (with P. Wagner), extended abstract in: Proceedings COCOA 2008, St. John's, Newfoundland, 2008, Lecture Notes in Computer Science 5165, 171-179
  7. Ptolemaic graphs and interval graphs are leaf powers, (with C. Hundt), extended abstract in: Proceedings LATIN 2008, Buzios near Rio 2008, Lecture Notes in Computer Science 4957, 479-491
  8. On (k,l)-leaf powers, (with P. Wagner), extended abstract in: Proceedings MFCS 2007, Cesky Krumlov 2007, Lecture Notes in Computer Science 4708, 525-535
  9. Generalized powers of graphs and their algorithmic use, (with F.F. Dragan, Y. Xiang and C. Yan, extended abstract in: Proceedings SWAT 2006, Riga 2006, Lecture Notes in Computer Science 4059, 423-434
  10. New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem, (with V.B. Le and S. Mahfud), extended abstract in: Proceedings FCT 2005, Lübeck, Lecture Notes in Computer Science 3623, 505-516, 2005
  11. Clique-Width for Four-Vertex Forbidden Subgraphs, (with H.-O. Le, J. Engelfriet and V.V. Lozin), extended abstract in: Proceedings FCT 2005, Lübeck, Lecture Notes in Computer Science 3623, 174-185, 2005
  12. On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem, (with Chinh T. Hoàng), extended abstract in: Proceedings IPCO 2005, Berlin, Lecture Notes in Computer Science 3509, 265-275
  13. Tree spanners for bipartite graphs and probe interval graphs, (with F.F. Dragan H.-O. Le, V.B. Le) and R. Uehara, extended abstract in: Proceedings 29th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG 2003, Elspeet 2003, Lecture Notes in Computer Science 2880, 106-118
  14. Linear time algorithms for some NP-complete problems on (P5,gem)-free graphs, (with Hans Bodlaender, Dieter Kratsch, Michael Rao and Jeremy Spinrad), extended abstract in: Proceedings International Conference FCT'2003, Malmö, Sweden, 2003, Lecture Notes in Computer Science 2751, 61-72
  15. New graph classes of bounded clique-width, (with F.F. Dragan H.-O. Le and R. Mosca), extended abstract in: Proceedings 28th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG 2002, Lecture Notes in Computer Science 2573, 57-67
  16. Tree spanners on chordal graphs: Complexity, algorithms, open problems, (with F.F. Dragan H.-O. Le and V.B. Le), extended abstract in: Proceedings International Conference ISAAC'2002, Vancouver, Canada, 2002, Lecture Notes in Computer Science 2518, 319-340
  17. On robust algorithms for the maximum weight stable set problem, Invited Talk, International Conference WEA'2001, Riga, Latvia, 2001, Lecture Notes in Computer Science 2138, 445-458
  18. Split-Perfect Graphs: Characterizations and Algorithmic Use (with V.B. Le), extended abstract in: Proceedings 26th International Workshop on Graph-Theoretic Concepts in Comp. Sci. (U. Brandes, D. Wagner, eds.) WG 2000, Lecture Notes in Computer Science 1928, 71-82
  19. Linear time algorithms for Hamiltonian problems on (claw,net)-free graphs (with F.F. Dragan and E. Köhler, extended abstract in: Conf. Proceedings 25th International Workshop on Graph-Theoretic Concepts in Comp. Sci. (P. Widmayer, G. Neyer, S. Eidenbenz, eds.) WG'99, Lecture Notes in Computer Science 1665, 364-376
  20. Distance approximating trees for chordal and dually chordal graphs (with V.D. Chepoi and F.F. Dragan), extended abstract in: Conf. Proceedings Algorithms ESA 1997 (R. Burkard, G. Woeginger, eds.) Lecture Notes in Computer Science 1284, 78-91
  21. LexBFS-orderings and powers of graphs (with F.F. Dragan and F. Nicolai), in: Proceedings 22nd International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'96 (F. d'Amore, P.G. Franciosa, A. Marchetti-Spaccamela, eds.), Lecture Notes in Computer Science 1197, 166-180
  22. Homogeneously orderable graphs and the Steiner tree problem (with F.F. Dragan and F. Nicolai), extended abstract in: Proceedings 21st International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'95, (M. Nagl, ed.), Lecture Notes in Computer Science 1017, 381-395
  23. The algorithmic use of hypertree structure and maximum neighbourhood orderings (with V.D. Chepoi and F.F. Dragan), extended abstract in: Proceedings 20th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'94, (G. Tinhofer, E.W. Mayr, G. Schmidt, eds.), Lecture Notes in Computer Science 903, 65-80
  24. Dually chordal graphs, (with F.F. Dragan, V.D. Chepoi and V.I. Voloshin), extended abstract in: Proceedings 19th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'93, (Jan van Leeuwen, ed.), Lecture Notes in Computer Science 790, 237-251
  25. Short disjoint cycles in graphs with degree constraints, (with H.-J. Voss), extended abstract in: Proceedings 19th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'93, (Jan van Leeuwen, ed.), Lecture Notes in Computer Science 790, 125-131
  26. r-Dominating cliques in graphs with hypertree structure, (with F.F. Dragan), extended abstract in: Proceedings Symposium on Theor. Aspects of Comp. Sci. STACS'94, Caen, France, (P. Enjalbert, E.W. Mayr, K.W. Wagner, eds.), Lecture Notes in Computer Science 775, 735-746
  27. On improved time bounds for permutation graph problems, in: Proceedings 18th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'92, (E.W. Mayr, ed.), Lecture Notes in Computer Science 657, 1-10
  28. Short disjoint cycles in cubic bridgeless graphs, in: Proceedings 17th International Workshop on Graph-Theoretic Concepts in Comp. Sci. WG'91, (G. Schmidt, R. Berghammer, eds.), Lecture Notes in Computer Science 570, 239-249
  29. On the domination problem for bipartite graphs, in: "Festschrift zu Ehren von Gerhard Ringel" (R. Bodendiek, R. Henn, eds.), Topics in Combinatorics and Graph Theory, Physica Verlag Heidelberg 1990, 145-152
  30. The jump number problem for biconvex graphs and rectangle covers of rectangular regions, in: Proceedings Conf. on Foundat. of Comput. Theory FCT'89, Lecture Notes in Computer Science 380, 68-77
  31. On the restriction of some NP-complete graph problems to permutation graphs, (with D. Kratsch), in: Proceedings Conf. on Foundat. of Comput. Theory FCT'85, Lecture Notes in Computer Science 199, 53-62
  32. Reversal-bounded and visit-bounded realtime computations, (with K.W. Wagner), in: Proceedings Conf. on Foundat. of Comput. Theory FCT'83, Lecture Notes in Computer Science 158, 26-39
  33. Pushdown automata with restricted use of storage symbols, in: Conf. Proceedings Math. Found. of Comput. Sci. MFCS'81, Lecture Notes in Computer Science 118, 234-241

Books and Edited Conference Proceedings

Recent Technical Reports and Talks

  1. On Independent Vertex Sets and Induced Matchings
  2. On Leaf Powers