Approximation algorithms for the maximally balanced connected graph tripartition problem

DOI10.1007/S10878-020-00544-WMaRDI QIDQ2082191zbMATH OpenOpenAlexFDO

Authors Guang-Ting Chen, Yong Chen, Zhi-Zhong Chen, Tian Liu, An Zhang, Guohui 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

2-connected componentapproximation algorithmconnected componentgraph partitioninduced subgraph

Mathematics Subject Classification ID

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

Recommendations

• 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
• Approximation algorithms for the maximum bounded connected bipartition problem
• Approximation and inaproximability results on balanced connected partitions of graphs

Cites work

• A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs
• A homology theory for spanning tress of a graph
• A polynomial algorithm for balanced clustering via graph partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation algorithms for maximally balanced connected graph partition
• Approximation Algorithms for Min–Max Tree Partition
• Approximation algorithms for minimum tree partition
• Approximation and inaproximability results on balanced connected partitions of graphs
• BALANCED PARTITION OF MINIMUM SPANNING TREES
• Efficient algorithms for a graph partitioning problem
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• scientific article; zbMATH DE number 432817 (Why is no real title available?)
• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Max-Min Tree Partitioning
• Max-min weight balanced connected partition
• On the complexity of graph tree partition problems.
• On the complexity of partitioning graphs into connected subgraphs
• Solving partition problems almost always requires pushing many vertices around

Cited in

(11)

• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Max-min weight balanced connected partition
• Approximation and inaproximability results on balanced connected partitions of 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
• Resource-limited network security games with general contagious attacks
• Algorithms for 2-balanced connected k-partition problem in graphs
• Algorithms for 2-balanced connected \(k\)-partition problem in graphs
• Approximation algorithm for the balanced 2-connected k-partition problem

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

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