On the Number of Minimal Separators in Graphs

DOI10.1007/978-3-662-53174-7_9zbMath1417.05105arXiv1503.01203OpenAlexW1594331173MaRDI QIDQ2827806

Simon MacKenzie, Serge Gaspers

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.01203

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Enumerating Minimal Tropical Connected Sets ⋮ On the Maximum Weight Minimal Separator

Cites Work

• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Exact exponential algorithms.
• Minimal triangulations of graphs: a survey
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Characterizations and algorithmic applications of chordal graph embeddings
• Efficient enumeration of all minimal separators in a graph
• Listing all potential maximal cliques of a graph
• Treewidth computation and extremal combinatorics
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• Large Induced Subgraphs via Triangulations and CMSO
• Finding Induced Subgraphs via Minimal Triangulations
• A measure & conquer approach for the analysis of exact algorithms
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• Exact Algorithms for Treewidth and Minimum Fill-In
• Listing all Minimal Separators of a Graph
• Combinatorial bounds via measure and conquer
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• On cliques in graphs

This page was built for publication: On the Number of Minimal Separators in Graphs