Approximation algorithm for the balanced 2-connected bipartition problem

DOI10.1007/978-3-319-08783-2_38MaRDI QIDQ2920480zbMATH OpenOpenAlexFDO

Authors Di Wu, Zhao Zhang, Weili Wu, Xiaohui Huang

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-08783-2_38

zbMATH Keywords

balanced \(m\)-connected \(k\)-partitionFPTASinterval graphpseudo-polynomial time algorithm

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Approximation algorithm for the balanced 2-connected k-partition problem
• Approximation algorithms for the maximum bounded connected bipartition problem
• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Approximation and inaproximability results on balanced connected partitions of graphs
• Approximation algorithms for maximally balanced connected graph partition

Cited in

(11)

• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Approximation algorithms for the maximum bounded connected bipartition problem
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• scientific article; zbMATH DE number 4101263 (Why is no real title available?)
• Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
• Max-min weight balanced connected partition
• An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Approximation and inaproximability results on balanced connected partitions of graphs
• Approximation and parameterized algorithms for balanced connected partition problems
• Approximation algorithm for the balanced 2-connected k-partition problem

This page was built for publication: Approximation algorithm for the balanced 2-connected bipartition problem

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