### Abstract

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

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 | Germany |

City | Berlin |

Period | 18/06/97 → 20/06/97 |

### Fingerprint

### Keywords

- METIS-140800
- IR-92412

### Cite this

*Graph-Theoretic Concepts in Computer Science*(pp. 109-117). (Lecture notes in computer science; Vol. 1335). Springer. https://doi.org/10.1007/BFb0024492

}

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

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

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 -