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

DOI10.1016/J.ENDM.2015.06.067zbMATH Open1346.05229OpenAlexW2173278659MaRDI QIDQ322301FDOQ322301

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

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

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)

Cites Work

• Balanced graph partitioning
• Some simplified NP-complete graph problems
• Title not available (Why is that?)
• Laplace eigenvalues of graphs---a survey
• Approximating minimum \(k\)-section in trees with linear diameter
• How Good is Recursive Bisection?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

Cited In (16)

• Problème de la bipartition minimale d'un graphe
• An exact combinatorial algorithm for minimum graph bisection
• On minimum bisection and related cut problems in trees and tree-like graphs
• Constrained domatic bipartition on trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating the minimum bisection size (extended abstract)
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating minimum \(k\)-section in trees with linear diameter
• Minimum bisection is NP-hard on unit disk graphs
• Bisection of bounded treewidth graphs by convolutions
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• Minimum bisection is fixed parameter tractable
• Title not available (Why is that?)

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)