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

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

doi:10.1007/BFb0024492

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

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

9 Citations (Scopus)

162 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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Publisher	Springer
Pages	109-117
Number of pages	19
ISBN (Print)	9783540637578
DOIs	https://doi.org/10.1007/BFb0024492
Publication status	Published - 1997
Event	23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997 - Berlin, Germany Duration: 18 Jun 1997 → 20 Jun 1997 Conference number: 23

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	1335
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997
Abbreviated title	WG
Country/Territory	Germany
City	Berlin
Period	18/06/97 → 20/06/97

Keywords

METIS-140800
IR-92412

Access to Document

10.1007/BFb0024492

chp_10.1007_BFb0024492

Cite this

@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",

address = "Germany",

note = "23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997, WG ; Conference date: 18-06-1997 Through 20-06-1997",

}

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

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.

N1 - Conference code: 23

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

T2 - 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1997

Y2 - 18 June 1997 through 20 June 1997

ER -

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

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this