Listing all Minimal Separators of a Graph
Authors:
- T. KloksTKT. Kloks
- D. KratschDKD. Kratsch
- 1 June 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (3) , 605-613
Abstract
An efficient algorithm listing all minimal vertex separators of an undirected graph is given. The algorithm needs polynomial time per separator that is found.Keywords
This publication has 15 references indexed in Scilit:
- On treewidth and minimum fill-in of asteroidal triple-free graphsTheoretical Computer Science, 1997
- Treewidth and Pathwidth of Permutation GraphsSIAM Journal on Discrete Mathematics, 1995
- Treewidth of Chordal Bipartite GraphsJournal of Algorithms, 1995
- Efficient Algorithms for Listing Combinatorial Structures1993
- Easy problems for tree-decomposable graphsJournal of Algorithms, 1991
- Linear time algorithms for NP-hard problems restricted to partial k-treesDiscrete Applied Mathematics, 1989
- Decomposition by clique separatorsDiscrete Mathematics, 1985
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A surveyBIT Numerical Mathematics, 1985
- An algorithm for finding clique cut-setsInformation Processing Letters, 1981
- Algorithms on clique separable graphsDiscrete Mathematics, 1977