Efficient enumeration of all minimal separators in a graph

DOI10.1016/S0304-3975(97)83809-1MaRDI QIDQ1390866zbMATH OpenOpenAlexFDO

Authors Hong Shen, W. Liang

Publication date 22 July 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(97)83809-1

zbMATH Keywords

minimal separators

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1420907
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Publication:4944975
• On the number of minimal separators in graphs
• On the number of minimal separators in graphs
• Efficiently enumerating minimal triangulations
• Listing all Minimal Separators of a Graph
• scientific article; zbMATH DE number 1796975
• Finding all minimum-size separating vertex sets in a graph
• scientific article; zbMATH DE number 7559431

Cites work

• scientific article; zbMATH DE number 432788 (Why is no real title available?)
• scientific article; zbMATH DE number 437524 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 1414319 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
• Computing connected components on parallel computers
• Efficient Algorithms for Listing Combinatorial Structures
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey

Cited in

(20)

• Linear separation of connected dominating sets in graphs
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• scientific article; zbMATH DE number 1796975 (Why is no real title available?)
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• A local approach to concept generation
• Finding all minimum-size separating vertex sets in a graph
• A linear time algorithm to list the minimal separators of chordal graphs
• Listing all the minimal separators of a 3-connected planar graph
• Depletable channels: dynamics, behaviour, and efficiency in network design
• On the number of minimal separators in graphs
• Approximately Counting Locally-Optimal Structures
• Disconnected matchings
• Disconnected matchings
• AMP chain graphs: minimal separators and structure learning algorithms
• scientific article; zbMATH DE number 1420907 (Why is no real title available?)
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Representing a concept lattice by a graph
• Approximately counting locally-optimal structures
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH

This page was built for publication: Efficient enumeration of all minimal separators in a graph

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