On the hardness of inclusion-wise minimal separators enumeration

DOI10.1016/J.IPL.2023.106469arXiv2308.15444OpenAlexW4389815725MaRDI QIDQ6195343FDOQ6195343

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

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

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)