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

Selected Publications

Papers in Refereed Journals:

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