Approximation algorithms for the maximally balanced connected graph tripartition problem

DOI10.1007/s10878-020-00544-wzbMath1502.90143OpenAlexW3006133478MaRDI QIDQ2082191

An Zhang, Tian Liu, Guangting Chen, Zhi-Zhong Chen, Yong Chen, Guo-Hui Lin

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00544-w

zbMATH Keywords

approximation algorithminduced subgraphconnected componentgraph partition2-connected component

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

Approximation and parameterized algorithms for balanced connected partition problems ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Max-min weight balanced connected partition
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Efficient algorithms for a graph partitioning problem
• On the complexity of partitioning graphs into connected subgraphs
• Approximation algorithms for minimum tree partition
• On the complexity of graph tree partition problems.
• A polynomial algorithm for balanced clustering via graph partitioning
• FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
• A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• A homology theory for spanning tress of a graph
• Approximation Algorithms for Min–Max Tree Partition
• BALANCED PARTITION OF MINIMUM SPANNING TREES
• Approximation algorithms for maximally balanced connected graph partition
• The complexity of tree partitioning

This page was built for publication: Approximation algorithms for the maximally balanced connected graph tripartition problem