On minimum bisection and related partition problems in graphs with bounded tree width

DOI10.1016/J.ENDM.2015.06.067MaRDI QIDQ322301zbMATH OpenOpenAlexFDO

Authors Cristina G. Fernandes, Tina Janne Schmidt, Anusch Taraz

Publication date 14 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2015.06.067

zbMATH Keywords

tree decompositionminimum bisectionminimum \(k\)-section

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On minimum bisection and related cut problems in trees and tree-like graphs
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Minimum bisection is fixed parameter tractable
• scientific article; zbMATH DE number 6303002
• Minimum bisection is fixed-parameter tractable

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 2086657 (Why is no real title available?)
• scientific article; zbMATH DE number 6303002 (Why is no real title available?)
• Approximating minimum \(k\)-section in trees with linear diameter
• Balanced graph partitioning
• How Good is Recursive Bisection?
• Laplace eigenvalues of graphs---a survey
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Some simplified NP-complete graph problems

Cited in

(17)

• scientific article; zbMATH DE number 6292751 (Why is no real title available?)
• Approximating the minimum bisection size (extended abstract)
• Bisection of bounded treewidth graphs by convolutions
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• scientific article; zbMATH DE number 3866593 (Why is no real title available?)
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• Problème de la bipartition minimale d'un graphe
• An exact combinatorial algorithm for minimum graph bisection
• Minimum bisection is NP-hard on unit disk graphs
• scientific article; zbMATH DE number 5237020 (Why is no real title available?)
• Minimum bisection is fixed parameter tractable
• Approximating minimum \(k\)-section in trees with linear diameter
• Solving cut-problems in quadratic time for graphs with bounded treewidth
• scientific article; zbMATH DE number 6303002 (Why is no real title available?)
• Constrained domatic bipartition on trees
• On minimum bisection and related cut problems in trees and tree-like graphs
• scientific article; zbMATH DE number 4131663 (Why is no real title available?)

This page was built for publication: On minimum bisection and related partition problems in graphs with bounded tree width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322301)