On the maximum weight minimal separator

DOI10.1016/J.TCS.2019.09.025MaRDI QIDQ2333804zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

treewidthminimal separatorparameterized algorithm

Mathematics Subject Classification ID

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)

Recommendations

• On the maximum weight minimal separator
• The \(k\)-separator problem
• The k-separator problem: polyhedra, complexity and approximation results
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• scientific article; zbMATH DE number 1500572

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity of Finding Embeddings in a k-Tree
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Exact Algorithms for Treewidth and Minimum Fill-In
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Graph minors. V. Excluding a planar graph
• Listing all potential maximal cliques of a graph
• Matching is as easy as matrix inversion
• Minimum Fill-in on Circle and Circular-Arc Graphs
• On the number of minimal separators in graphs
• Parameterized algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Some simplified NP-complete graph problems
• The disjoint paths problem in quadratic time
• Towards tight(er) bounds for the excluded grid theorem
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth. Computations and approximations

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)