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

Selected Publications

Papers in Refereed Journals:

  1. A Forbidden Induced Subgraph Characterization of Distance-Hereditary 5-Leaf Powers, (with V.B. Le and D. Rautenbach), accepted for Discrete Mathematics
  2. Structure and Linear Time Recognition of 4-Leaf Powers, (with V.B. Le and R. Sritharan), to appear in ACM Transactions on Algorithms
  3. On independent vertex sets in subclasses of apple-free graphs, (with T. Klembt, V.V. Lozin and R. Mosca), appeared online in Algorithmica
  4. 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
  5. Maximum induced matching for chordal graphs in linear time, (with Chinh T. Hoàng), appeared online in Algorithmica
  6. 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
  7. 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
  8. 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
  9. Structure and linear time recognition of 3-leaf powers, (with V.B. Le), Information Processing Letters 98 (2006) 133-138
  10. 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
  11. 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
  12. 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
  13. Bisplit graphs (with P.L. Hammer, V.B. Le and V.V. Lozin), Discrete Mathematics 299 (2005) 11-32
  14. 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
  15. On the structure of (P5,gem)-free graphs, (with D. Kratsch), Discrete Applied Mathematics 145 (2005) 155-166
  16. 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
  17. 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
  18. 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
  19. (P5,Diamond)-Free Graphs Revisited: Structure and Linear Time Optimization, Discrete Applied Mathematics 138 (2004) 13-27
  20. 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
  21. Split-Perfect Graphs: Characterizations and Algorithmic Use (with V.B. Le), SIAM J. Discrete Math. 17 (2004) 341-360
  22. 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
  23. On the Structure and Stability Number of P5- and Co-Chair-Free Graphs, (with R. Mosca), Discrete Applied Mathematics 132 (2004) 47-65
  24. 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
  25. On linear and circular structure of (claw,net)-free graphs, (with F.F. Dragan), Discrete Applied Mathematics 129 (2003) 285-303
  26. On variations of P4-sparse graphs, (with R. Mosca), Discrete Applied Mathematics 129 (2003) 521-532
  27. On the linear structure and clique width of bipartite permutation graphs, (with V.V. Lozin), Ars Combinatoria Vol. LXVII (2003) 273-281
  28. 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
  29. 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
  30. 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
  31. On $\alpha$-redundant vertices in P5-free graphs (with H.-O. Le and V.B. Le), Information Processing Letters 82 (2002) 119-122
  32. A note on $\alpha$-redundant vertices in graphs (with V.V. Lozin), Discrete Applied Mathematics 108 (2001) 301-308
  33. 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
  34. 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
  35. On stable cutsets in graphs (with F.F. Dragan, V.B. Le and T. Szymczak), Discrete Applied Mathematics 105 (2000) 39-50
  36. Recognizing the P4-structure of block graphs (with V.B. Le), Discrete Applied Mathematics 99 (2000) 349-366
  37. Distance approximating trees for chordal and dually chordal graphs (with V.D. Chepoi and F.F. Dragan), J. Algorithms 30 (1999) 166-184
  38. Tree- and Forest-Perfect Graphs (with V.B. Le), Discrete Applied Mathematics 95 (1999) 141-162
  39. On the stability number of claw-free P5-free and more general graphs (with P.L. Hammer), Discrete Applied Mathematics 95 (1999) 163-167
  40. Recognizing the P4-structure of bipartite graphs (with L. Babel and V.B. Le), Discrete Applied Mathematics 93 (1999) 157-168
  41. Convexity and HHD-free graphs (with F.F. Dragan and F. Nicolai), SIAM J. Discrete Math. 12 (1999) 119-135
  42. The complexity of some problems related to graph 3-colorability (with V.B. Le and T. Szymczak), Discrete Applied Mathematics 89 (1998) 59-73
  43. A Linear-Time Algorithm for Connected r-Domination and Steiner Tree on Distance-Hereditary Graphs (with F.F. Dragan), Networks 31 (1998) 177-182
  44. 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
  45. Dually chordal graphs (with F.F. Dragan, V.D. Chepoi and V.I. Voloshin), SIAM J. Discrete Math. 11 (1998) 437-455
  46. Powers of HHD-free graphs (with F.F. Dragan and F. Nicolai), Internat. Journal of Computer Mathematics 69 (1998) 217-242
  47. Duchet-Type Theorems for powers of HHD-free graphs (with V.B. Le and T. Szymzcak), Discrete Mathematics 177 (1997) 9-16
  48. LexBFS-orderings and powers of chordal graphs (with F.F. Dragan and F. Nicolai), Discrete Mathematics 171 (1997) 27-42
  49. Homogeneously orderable graphs (with F.F. Dragan and F. Nicolai), Theoretical Computer Science 172 (1997) 209-232
  50. 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
  51. r-Dominating cliques in graphs with hypertree structure (with F.F. Dragan), Discrete Mathematics 162 (1996) 93-108
  52. Perfect elimination orderings of chordal powers of graphs (with V.D. Chepoi and F.F. Dragan), Discrete Mathematics 158 (1996) 273-278
  53. Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics 152 (1996) 47-54; Corrigendum: Discrete Mathematics 186 (1998) 295
  54. Short disjoint cycles in graphs with degree constraints (with H.-J. Voss), Discrete Applied Mathematics 64 (1996) 197-205
  55. Classes of bipartite graphs related to chordal graphs, Discrete Applied Mathematics 32 (1991), 51-60
  56. Uniform simulations of nondeterministic real time multitape Turing machines, (with F.J. Brandenburg and K.W. Wagner), Math. Systems Theory 19 (1987) 277-299
  57. Bipartite permutation graphs (with J.P. Spinrad and L.K. Stewart), Discrete Applied Mathematics 18 (1987) 279-292
  58. On domination problems for permutation and other graphs (with D. Kratsch), Theoretical Computer Science 54 (1987) 181-198
  59. The NP-completeness of STEINER TREE and DOMINATING SET for chordal bipartite graphs (with H. Müller), Theoretical Computer Science 53 (1987) 257-265
  60. 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
  61. Bipartite permutation graphs are bipartite tolerance graphs (with J.P. Spinrad and L.K. Stewart), Congressus Numerantium 58 (1987) 165-174
  62. On partitions of permutations into increasing and decreasing subsequences (with D. Kratsch) Elektron. Informationsverarb. u. Kybernetik 22 (1986) 5/6, 263-273
  63. Space classes, intersections of languages and bounded erasing homomorphisms, R.A.I.R.O. Informatique Theorique 17 (1983) 121-130
  64. 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
  65. A relation between space, return and dual return complexities (with G. Wechsung), Theoretical Computer Science 9 (1979) 127-140
  66. On a property of homogeneous Gaussian L-fields (in Russian), Teorija werojatnostjej i jejo primenenija (Probability Theory and its Applications) 3 (1979), 596-600
  67. On a family of complexity measures on Turing machines defined by predicates, Elektron. Inf.verarb. u. Kybern. 14 (1978) 11, 331-339
  68. 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. 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, LNCS 2008.
  2. 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, LNCS 2008.
  3. Independent Sets of Maximum Weight in Apple-Free Graphs, (with T. Klembt, V.V. Lozin and R. Mosca), extended abstract to appear in: Proceedings ISAAC 2008, Gold Coast, Australia, 2008, LNCS 2008.
  4. Simplicial powers of graphs, (with V.B. Le), extended abstract in: Proceedings COCOA 2008, St. John's, Newfoundland, 2008, LNCS 5165, 160-170, 2008.
  5. On k- versus (k+1)-leaf powers, (with P. Wagner), extended abstract in: Proceedings COCOA 2008, St. John's, Newfoundland, 2008, LNCS 5165, 171-179, 2008.
  6. Ptolemaic graphs and interval graphs are leaf powers, (with C. Hundt), extended abstract in: Proceedings LATIN 2008, Buzios near Rio 2008, LNCS 4957, 479-491
  7. On (k,l)-leaf powers, (with P. Wagner), extended abstract in: Proceedings MFCS 2007, Cesky Krumlov 2007, LNCS 4708, 525-535
  8. 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, LNCS 4059, 423-434
  9. 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, LNCS 3623, 505-516, 2005
  10. 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, LNCS 3623, 174-185, 2005
  11. 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, LNCS 3509, 265-275
  12. 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, LNCS 2880, 106-118
  13. 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, LNCS 2751, 61-72
  14. 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, 163-174
  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. 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
  17. 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. WG 2000, Lecture Notes in Computer Science 1928, 71-82 (U. Brandes, D. Wagner, eds.)
  18. 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. WG'99, Lecture Notes in Computer Science 1665, 364-376, (P. Widmayer, G. Neyer, S. Eidenbenz, eds.)
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  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. On some 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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

  1. Strictly Chordal Graphs Are Precisely (4,6)-Leaf Powers
  2. Gem- and Co-Gem-Free Graphs Have Bounded Clique-Width
  3. Chordal co-gem-free and (P5,gem)-free graphs have bounded clique-width
  4. On the Structure of (P5,Gem)-Free Graphs
  5. On Minimal Prime Extensions of a Four-Vertex Graph in a Prime Graph
  6. New Graph Classes of Bounded Clique-Width
  7. On variations of P4-sparse graphs
  8. Structure and Stability Number of Chair-,Co-P- and Gem-Free Graphs Revisited
  9. On the Structure and Stability Number of P5- and Co-Chair-Free Graphs
  10. Efficient Robust Algorithms for the Maximum Weight Stable Set Problem in Chair-free Graph Classes
  11. Bisplit Graphs
  12. On clique separators, nearly chordal graphs and the Maximum Weight Stable Set Problem
  13. Clique-Width for Four-Vertex Forbidden Subgraphs