On the maximum weight minimal separator
DOI10.1016/J.TCS.2019.09.025zbMATH Open1435.68239OpenAlexW2976984178MaRDI QIDQ2333804FDOQ2333804
Authors: Tesshu Hanaka, Tom C. van der Zanden, Hirotaka Ono, 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Complexity of Finding Embeddings in a k-Tree
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized algorithms
- Graph minors. V. Excluding a planar graph
- Some simplified NP-complete graph problems
- The disjoint paths problem in quadratic time
- Treewidth. Computations and approximations
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Title not available (Why is that?)
- Matching is as easy as matrix inversion
- Listing all potential maximal cliques of a graph
- Treewidth and minimum fill-in: Grouping the minimal separators
- Exact Algorithms for Treewidth and Minimum Fill-In
- Treewidth and Pathwidth of Permutation Graphs
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Minimum Fill-in on Circle and Circular-Arc Graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- On the number of minimal separators in graphs
- Title not available (Why is that?)
- Towards tight(er) bounds for the excluded grid theorem
Cited In (12)
- Bisimplicial separators
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- In)approximability of Maximum Minimal FVS
- The \(k\)-separator problem
- Solving the weighted \(k\)-separator problem in graphs with specific modules
- On the maximum weight minimal separator
- Parameterized complexity of immunization in the threshold model
- Immunization in the threshold model: a parameterized complexity study
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- (In)approximability of maximum minimal FVS
- MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS
This page was built for publication: On the maximum weight minimal separator
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333804)
