On the hardness of inclusion-wise minimal separators enumeration

DOI10.1016/J.IPL.2023.106469MaRDI QIDQ6195343zbMATH OpenOpenAlexFDO

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

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

• scientific article; zbMATH DE number 7764121 (Why is no real title available?)
• A note on the complexity of the chromatic number problem
• Algorithmic graph theory and perfect graphs
• Exact Algorithms for Treewidth and Minimum Fill-In
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Listing all Minimal Separators of a Graph
• Listing all potential maximal cliques of a graph
• On generating all maximal independent sets
• On the number of minimal separators in graphs
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Positive-instance driven dynamic programming for treewidth
• Small Maximal Independent Sets and Faster Exact Graph Coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195343)