### Abstract

Original language | English |
---|---|

Pages (from-to) | 367-400 |

Number of pages | 34 |

Journal | Discrete applied mathematics |

Volume | 99 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 2000 |

### Fingerprint

### Keywords

- Chordal graphs
- Fragment tree
- Minimum fill-in
- Distance hereditary graphs
- Tree representation
- Treewidth
- Linear time algorithm

### Cite this

*Discrete applied mathematics*,

*99*(1-3), 367-400. https://doi.org/10.1016/S0166-218X(99)00146-8

}

*Discrete applied mathematics*, vol. 99, no. 1-3, pp. 367-400. https://doi.org/10.1016/S0166-218X(99)00146-8

**A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs.** / Broersma, Haitze J.; Dahlhaus, E.; Kloks, A.J.J.; Kloks, T.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs

AU - Broersma, Haitze J.

AU - Dahlhaus, E.

AU - Kloks, A.J.J.

AU - Kloks, T.

PY - 2000

Y1 - 2000

N2 - A graph is distance hereditary if it preserves distances in all its connected induced subgraphs. 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 paper we show that both problems are solvable in linear time for distance hereditary graphs.

AB - A graph is distance hereditary if it preserves distances in all its connected induced subgraphs. 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 paper we show that both problems are solvable in linear time for distance hereditary graphs.

KW - Chordal graphs

KW - Fragment tree

KW - Minimum fill-in

KW - Distance hereditary graphs

KW - Tree representation

KW - Treewidth

KW - Linear time algorithm

U2 - 10.1016/S0166-218X(99)00146-8

DO - 10.1016/S0166-218X(99)00146-8

M3 - Article

VL - 99

SP - 367

EP - 400

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 1-3

ER -