Algorithms for the treewidth and minimum fill-in of HHD-free graphs

Haitze J. Broersma, E. Dahlhaus, A.J.J. Kloks, T. Kloks

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

6 Citations (Scopus)
84 Downloads (Pure)

Abstract

A graph is HHD-free is it does not contain a house (i.e., the complement of P 5), a hole (a cycle of length at least 5) or a domino (the graph obtained from two 4-cycles by identifying an edge in one C 4 with an edge in the other C 4) as an induced subgraph. The minimum fill-in problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The treewidth problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this note we show that both problems are solvable in polynomial time for HHD-free graphs.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
PublisherSpringer
Pages109-117
Number of pages19
ISBN (Print)9783540637578
DOIs
Publication statusPublished - 1997
Event23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997 - Berlin, Germany
Duration: 18 Jun 199720 Jun 1997
Conference number: 23

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume1335
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997
Abbreviated titleWG
CountryGermany
CityBerlin
Period18/06/9720/06/97

Keywords

  • METIS-140800
  • IR-92412

Fingerprint Dive into the research topics of 'Algorithms for the treewidth and minimum fill-in of HHD-free graphs'. Together they form a unique fingerprint.

Cite this