On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators

DOI10.1007/978-3-662-53536-3_16zbMath1417.05227arXiv1607.04545OpenAlexW2508369034MaRDI QIDQ3181057

Ioan Todinca, Pedro Montealegre

Publication date: 22 December 2016

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Unnamed Item ⋮ Linear separation of connected dominating sets in graphs ⋮ Structurally parameterized \(d\)-scattered set ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Vertex cover at distance on \(H\)-free graphs

Cites Work

• Unnamed Item
• Finding clubs in graph classes
• Domination in convex and chordal bipartite graphs
• Local complementation and interlacement graphs
• Listing all potential maximal cliques of a graph
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Parameterized domination in circle graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Large Induced Subgraphs via Triangulations and CMSO
• Finding Induced Subgraphs via Minimal Triangulations
• Algorithmic Aspects of Vertex Elimination on Graphs
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Two-Connected Augmentation Problems in Planar Graphs
• Treewidth and Pathwidth of Permutation Graphs
• Kernelization Lower Bounds Through Colors and IDs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Brief Announcement

This page was built for publication: On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators