Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph

DOI10.1016/j.dam.2010.05.013zbMath1201.05098OpenAlexW1987604867MaRDI QIDQ602684

Ken Takata

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.05.013

zbMATH Keywords

graph algorithmsbacktrackingpolynomial spacelisting algorithmsminimal vertex separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Polynomial-delay and polynomial-space enumeration of large maximal matchings ⋮ Unnamed Item ⋮ Efficient enumeration of maximal induced bicliques ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ Unnamed Item ⋮ Separators and adjustment sets in causal graphs: complete criteria and an algorithmic framework

Cites Work

• Unnamed Item
• Safe separators for treewidth
• On generating all maximal independent sets
• Efficient enumeration of all minimal separators in a graph
• Representing a concept lattice by a graph
• A local approach to concept generation
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
• Efficient Algorithms for Listing Combinatorial Structures
• Listing all Minimal Separators of a Graph