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

DOI10.1016/J.TCS.2015.02.001zbMATH Open1333.68298OpenAlexW2063081927MaRDI QIDQ896161FDOQ896161

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

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)

Cites Work

• On the approximability of some Maximum Spanning Tree Problems
• Most uniform path partitioning and its use in image processing
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• On the complexity of partitioning graphs into connected subgraphs
• A homology theory for spanning tress of a graph
• Clustering on trees
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• Approximation Algorithm for the Balanced 2-Connected Bipartition Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Reconfiguration of connected graph partitions via recombination
• An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment
• 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
• Approximation and parameterized algorithms for balanced connected partition problems

Recommendations

• Approximating the Maximally Balanced Connected Partition Problem in graphs 👍 👎
• Approximation algorithms for maximally balanced connected graph partition 👍 👎
• Approximation algorithms for maximally balanced connected graph partition 👍 👎
• Approximation and parameterized algorithms for balanced connected partition problems 👍 👎
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds 👍 👎
• Approximation algorithms for the maximally balanced connected graph tripartition problem 👍 👎
• Approximation algorithms for the maximum bounded connected bipartition problem 👍 👎
• Approximation Algorithm for the Balanced 2-Connected Bipartition Problem 👍 👎
• Algorithms for the Balanced Edge Partitioning Problem 👍 👎
• Title not available (Why is that?) 👍 👎

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)