Lexbfs-orderings and powers of hhd-free graphs Footnote^∗

First author supported by VW, Project No. I/69041 and by DFG, second author supported by DFG

References

• Bandelt , H. J. , Henkmann , A. and Nicolai , F. 1995 . Powers of distance-hereditary graphs . Discrete Math , 145 : 37 – 60 .
   Google Scholar
• Brandstadt , A. , Chepoi , V. D. and Dragan , F. F. 1998 . “ The algorithmic use of hypertree structure and maximum neighborhood orderings, 20th International Workshop ” . In Graph-Theoretic Concepts in Computer Science” WG'94 Herrsching , Edited by: Mayr , E. W. , Schmidt , G. and Tinhofer , G. 65 – 80 . Germany : Springer . LNCS 903 1995, Discrete Appl. Math., 82, 43-77
   Google Scholar
• Brandstädt , A. , Dragan , F. F. and Nicolai , F. 1997 . LexBFS-orderings and powers of chordal graphs . Technical Report Gerhard-Mercator-Universität-Gesamthochschule Duisburg SM-DU-287, Discrete Math , 171 : 27 – 42 .
   Google Scholar
• Brandstädt , A. , Bang Le , Van and Szymczak , Th. 1997 . Duchet-type Theorems for Powers of HHD-free graphs . Discrete Math , 177 : 9 – 16 .
   Web of Science ®Google Scholar
• Chandrasekaran , R. and Doughety , A. 1981 . Location on tree networks: p-center and q-dispersion problems . Math. Oper. Res , 6 : 50 – 57 .
   Web of Science ®Google Scholar
• Chang , G. J. and Nemhauser , G. L. 1984 . The k-domination and k-stability problems on sun-free chordal graphs . SIAM J. Algebraic and Discrete Methods , 5 : 332 – 345 .
   Google Scholar
• Chepoi , V. D. 1986 . Some properties of d-convexity in triangulated graphs . Mathematical Researches (Chişin[acaron]u) , 87 : 164 – 177 . (in Russian)
   Google Scholar
• Chepoi V. D. Dragan F. F. Computing a central vertex of a HHD-free graph in preparation
   Google Scholar
• Chvatal , V. 1984 . Perfectly orderable graphs . Annals of Discrete Math , 21 : 63 – 65 .
   Google Scholar
• Dirac , G. A. 1961 . On rigid circuit graphs . Abh. Math. Seminar Univ. Hamburg , 25 : 71 – 76 .
   Google Scholar
• Dragan F. F. Nicolai F. LexBFS-orderings and distance-hereditary graphs Technical Report Gerhard-Mercator-Universität - Gesamthochschule Duisburg SM-DU 1995 303
   Google Scholar
• Dragan F. F. Nicolai F. Brandstädt A Convexity and HHD-free graphs Technical Report Gerhard-Mercator-Universitat - Gesamthochschule Duisburg SM-DU 1995 290 to appear in SIAM J. Discrete Math
   Google Scholar
• Dragan F. F. Nicolai F. Brandstädt A Powers of HHD-free graphs Technical Report Gerhard-Mercator-Universitat - Gesamthochschule Duisburg SM-DU 1995 315 to appear in SIAM J. Discrete Math
   Google Scholar
• Duchet , P. 1984 . Classical perfect graphs . Annals of Discrete Math , 21 : 67 – 96 .
   Google Scholar
• Fulkerson , D. R. and Gross , O. A. 1965 . Incidence matrices and interval graphs . Pacific J. Math , 15 : 835 – 855 .
   Web of Science ®Google Scholar
• Gionfriddo , M. 1986 . A short survey on some generalized colorings of graphs . Ars Comb , 30 : 275 – 284 .
   Google Scholar
• Golumbic , M. C. 1980 . Algorithmic Graph Theory and Perfect Graphs , New York : Academic Press .
   Google Scholar
• Hoàng , C. T. and Khouzam , K. 1988 . On Brittle graphs . J. Graph Theory , 12 : 391 – 404 .
   Google Scholar
• Howorka , E. 1977 . A characterization of distance-hereditary graphs . Quart. J. Math. Oxford, Ser , 28 ( 2 ) : 417 – 420 .
   Google Scholar
• Jamison , B. and Olariu , S. 1988 . On the semi-perfect elimination . Advances in Applied Math , 9 ( 2 ) : 364 – 376 .
   Google Scholar
• Jensen , T. R. and Toft , B. 1995 . Graph coloring problems , Wiley .
   Google Scholar
• Kloks , T. , Kratsch , D. and Müller , H. 1995 . “ Approximating the bandwidth for AT-free graphs ” . In Proceedings of European Symposium on Algorithms ESA '95 , Edited by: Spirakis , P. 434 – 447 . Springer . LNCS 979
   Google Scholar
• Olariu , S. 1989 . Weak bipolarizabie graphs . Discrete Math , 74 : 159 – 171 .
   Google Scholar
• Rose , D. , Tarjan , R. E. and Lueker , G. 1976 . Algorithmic aspects on vertex elimination on graphs . SIAM J. Computing , 5 : 266 – 283 .
   Google Scholar