GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
From MaRDI portal
Publication:5249047
DOI10.1142/S0129054100000211zbMath1320.05120OpenAlexW2031076941MaRDI QIDQ5249047
Olivier Cogis, Jean-Paul Bordat, Anne Berry
Publication date: 29 April 2015
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054100000211
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (34)
Minimal triangulations of graphs: a survey ⋮ A linear time algorithm to list the minimal separators of chordal graphs ⋮ Listing all the minimal separators of a 3-connected planar graph ⋮ Minimal separators in \(P_4\)-sparse graphs ⋮ Representing a concept lattice by a graph ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ A local approach to concept generation ⋮ Treewidth computation and extremal combinatorics ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Some results on connected vertex separators ⋮ A new characterization of unichord-free graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Unnamed Item ⋮ On the hardness of inclusion-wise minimal separators enumeration ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Maximum Weight Minimal Separator ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ Minimal separators in extended \(P_4\)-laden graphs ⋮ Graphical models for genetic analyses ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ Conditions for swappability of records in a microdata set when some marginals are fixed ⋮ Linear separation of connected dominating sets in graphs ⋮ On the Number of Minimal Separators in Graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Minimal separators in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>P</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-tidy graphs ⋮ On the maximum weight minimal separator ⋮ Observability-blocking control using sparser and regional feedback for network synchronization processes ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
Cites Work
- Efficient enumeration of all minimal separators in a graph
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Separability generalizes Dirac's theorem
- A fast algorithm for building lattices
- Schnittverbände in Graphen. (Intersection lattices in graphs)
- Listing all Minimal Separators of a Graph
- Treewidth and Pathwidth of Permutation Graphs
This page was built for publication: GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH