Listing all Minimal Separators of a Graph

DOI10.1137/S009753979427087XMaRDI QIDQ4388888zbMATH OpenFDO

Authors Ton Kloks, Dieter Kratsch

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S009753979427087X

zbMATH Keywords

algorithmgood pairgraphlisting algorithmminimal pairminimal separator

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(34)

• Efficient enumeration of all minimal separators in a graph
• On treewidth approximations.
• Listing all potential maximal cliques of a graph
• The k-hop connected dominating set problem: approximation and hardness
• Minimal separators in extended \(P_4\)-laden graphs
• Representing a concept lattice by a graph
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Observability-blocking control using sparser and regional feedback for network synchronization processes
• Conditions for swappability of records in a microdata set when some marginals are fixed
• A local approach to concept generation
• Treewidth computation and extremal combinatorics
• Depletable channels: dynamics, behaviour, and efficiency in network design
• On the number of minimal separators in graphs
• Minimal separators in P₄-tidy graphs
• Vertex ranking of asteroidal triple-free graphs
• Approximately counting locally-optimal structures
• Approximately Counting Locally-Optimal Structures
• Ordered coloring of grids and related graphs
• Listing all spanning trees in Halin graphs -- sequential and parallel view
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Linear separation of connected dominating sets in graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Separator orders in interval, cocomparability, and AT-free graphs
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• Some results on connected vertex separators
• On the hardness of inclusion-wise minimal separators enumeration
• Comparison of k-creature and t-critter
• Isolated scattering number can be computed in polynomial time for interval graphs
• 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
• A new characterization of unichord-free graphs
• Chordal Coxeter groups.
• On probe permutation graphs

This page was built for publication: Listing all Minimal Separators of a Graph

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