Approximation algorithm for the balanced 2-connected k-partition problem

DOI10.1016/J.TCS.2015.02.001MaRDI QIDQ896161zbMATH OpenOpenAlexFDO

Authors Di Wu, Zhao Zhang, Weili Wu

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.001

zbMATH Keywords

FPTASinterval graphpseudo-polynomial time algorithmbalanced \(m\)-connected \(k\)-partition

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithm for the balanced 2-connected bipartition problem
• Approximation and parameterized algorithms for balanced connected partition problems
• Approximation algorithms for maximally balanced connected graph partition
• Approximation algorithms for maximally balanced connected graph partition
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Improved approximation algorithms for balanced partitioning problems
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• Algorithms for the Balanced Edge Partitioning Problem
• Approximation algorithms for the maximum bounded connected bipartition problem
• Approximation algorithms for the maximally balanced connected graph tripartition problem

Cites work

• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A homology theory for spanning tress of a graph
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation algorithm for the balanced 2-connected bipartition problem
• Approximation and inaproximability results on balanced connected partitions of graphs
• Clustering on trees
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• Graph theory with applications
• Most uniform path partitioning and its use in image processing
• On the approximability of some Maximum Spanning Tree Problems
• On the complexity of partitioning graphs into connected subgraphs

Cited in

(11)

• Cut and flow formulations for the balanced connected \(k\)-partition problem
• Approximation and parameterized algorithms for balanced connected partition problems
• Approximation algorithms for the maximum bounded connected bipartition problem
• Reconfiguration of connected graph partitions via recombination
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment
• Approximation algorithm for the balanced 2-connected bipartition problem
• Max-min weight balanced connected partition
• An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
• Reconfiguration of connected graph partitions via recombination
• Approximation algorithms for maximally balanced connected graph partition

This page was built for publication: Approximation algorithm for the balanced 2-connected \(k\)-partition problem

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