FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS

DOI10.1142/S179383091250005XzbMath1253.68366OpenAlexW1967968533MaRDI QIDQ2905305

Bang Ye Wu

Publication date: 27 August 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s179383091250005x

zbMATH Keywords

approximation algorithminterval graphFPTASconnected partition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

An overview of graph covering and partitioning ⋮ Approximation algorithms for the maximum bounded connected bipartition problem ⋮ Max-min weight balanced connected partition ⋮ Approximation and parameterized algorithms for balanced connected partition problems ⋮ Approximation algorithm for the balanced 2-connected \(k\)-partition problem ⋮ Cardinality constrained connected balanced partitions of trees under different criteria ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Uniform and most uniform partitions of trees ⋮ Partitioning a graph into balanced connected classes: formulations, separation and experiments ⋮ Approximation algorithms for maximally balanced connected graph partition ⋮ Approximation algorithms for the maximally balanced connected graph tripartition problem ⋮ Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

Cites Work

• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• A linear algorithm for bipartition of biconnected graphs
• On the complexity of partitioning graphs into connected subgraphs
• On the approximability of some Maximum Spanning Tree Problems
• Max-Min Tree Partitioning
• A homology theory for spanning tress of a graph
• Max-min partitioning of grid graphs into connected components

This page was built for publication: FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS