On the hardness of inclusion-wise minimal separators enumeration

DOI10.1016/j.ipl.2023.106469arXiv2308.15444OpenAlexW4389815725MaRDI QIDQ6195343

Kunihiro Wasa, Caroline Brosse, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, Oscar Defrain

Publication date: 13 March 2024

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2308.15444

zbMATH Keywords

combinatorial problemsminimal separatorsoutput-sensitive enumeration\(\mathsf{NP}\)-hardnessinclusion-wise minimal separators

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• On generating all maximal independent sets
• A note on the complexity of the chromatic number problem
• Listing all potential maximal cliques of a graph
• Algorithmic graph theory and perfect graphs
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Positive-instance driven dynamic programming for treewidth
• Exact Algorithms for Treewidth and Minimum Fill-In
• Listing all Minimal Separators of a Graph
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• On the number of minimal separators in graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH

This page was built for publication: On the hardness of inclusion-wise minimal separators enumeration