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

7 Citations (Scopus)
56 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

Fingerprint

Treewidth
Graph in graph theory
Cycle
Clique number
Induced Subgraph
Polynomial time
Complement

Keywords

  • METIS-140800
  • IR-92412

Cite this

Broersma, H. J., Dahlhaus, E., Kloks, A. J. J., & Kloks, T. (1997). Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In Graph-Theoretic Concepts in Computer Science (pp. 109-117). (Lecture notes in computer science; Vol. 1335). Springer. https://doi.org/10.1007/BFb0024492
Broersma, Haitze J. ; Dahlhaus, E. ; Kloks, A.J.J. ; Kloks, T. / Algorithms for the treewidth and minimum fill-in of HHD-free graphs. Graph-Theoretic Concepts in Computer Science. Springer, 1997. pp. 109-117 (Lecture notes in computer science).
@inproceedings{73704480065945618b0f743c092506d0,
title = "Algorithms for the treewidth and minimum fill-in of HHD-free graphs",
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.",
keywords = "METIS-140800, IR-92412",
author = "Broersma, {Haitze J.} and E. Dahlhaus and A.J.J. Kloks and T. Kloks",
year = "1997",
doi = "10.1007/BFb0024492",
language = "English",
isbn = "9783540637578",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "109--117",
booktitle = "Graph-Theoretic Concepts in Computer Science",

}

Broersma, HJ, Dahlhaus, E, Kloks, AJJ & Kloks, T 1997, Algorithms for the treewidth and minimum fill-in of HHD-free graphs. in Graph-Theoretic Concepts in Computer Science. Lecture notes in computer science, vol. 1335, Springer, pp. 109-117, 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997, Berlin, Germany, 18/06/97. https://doi.org/10.1007/BFb0024492

Algorithms for the treewidth and minimum fill-in of HHD-free graphs. / Broersma, Haitze J.; Dahlhaus, E.; Kloks, A.J.J.; Kloks, T.

Graph-Theoretic Concepts in Computer Science. Springer, 1997. p. 109-117 (Lecture notes in computer science; Vol. 1335).

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

TY - GEN

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

AU - Broersma, Haitze J.

AU - Dahlhaus, E.

AU - Kloks, A.J.J.

AU - Kloks, T.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - METIS-140800

KW - IR-92412

U2 - 10.1007/BFb0024492

DO - 10.1007/BFb0024492

M3 - Conference contribution

SN - 9783540637578

T3 - Lecture notes in computer science

SP - 109

EP - 117

BT - Graph-Theoretic Concepts in Computer Science

PB - Springer

ER -

Broersma HJ, Dahlhaus E, Kloks AJJ, Kloks T. Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In Graph-Theoretic Concepts in Computer Science. Springer. 1997. p. 109-117. (Lecture notes in computer science). https://doi.org/10.1007/BFb0024492