Approximation algorithm for the balanced 2-connected \(k\)-partition problem

DOI10.1016/j.tcs.2015.02.001zbMath1333.68298OpenAlexW2063081927MaRDI QIDQ896161

Zhao Zhang, Weili Wu, Di 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

interval graphFPTASpseudo-polynomial time algorithmbalanced \(m\)-connected \(k\)-partition

Mathematics Subject Classification ID

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

Related Items (2)

Reconfiguration of connected graph partitions via recombination ⋮ Reconfiguration of connected graph partitions via recombination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• On the complexity of partitioning graphs into connected subgraphs
• On the approximability of some Maximum Spanning Tree Problems
• Clustering on trees
• Most uniform path partitioning and its use in image processing
• FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
• Approximation Algorithm for the Balanced 2-Connected Bipartition Problem
• A homology theory for spanning tress of a graph

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