On the maximum weight minimal separator
From MaRDI portal
Publication:2333804
DOI10.1016/j.tcs.2019.09.025zbMath1435.68239OpenAlexW2976984178MaRDI QIDQ2333804
Hirotaka Ono, Tom C. van der Zanden, Tesshu Hanaka, Hans L. Bodlaender
Publication date: 13 November 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.025
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items
Parameterized complexity of immunization in the threshold model ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ In)approximability of Maximum Minimal FVS ⋮ (In)approximability of maximum minimal FVS ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- Graph minors. V. Excluding a planar graph
- Matching is as easy as matrix inversion
- Some simplified NP-complete graph problems
- Treewidth. Computations and approximations
- Listing all potential maximal cliques of a graph
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Exact Algorithms for Treewidth and Minimum Fill-In
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Complexity of Finding Embeddings in a k-Tree
- Minimum Fill-in on Circle and Circular-Arc Graphs
- On the number of minimal separators in graphs
- Treewidth and Pathwidth of Permutation Graphs
- Towards Tight(er) Bounds for the Excluded Grid Theorem
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
