FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
From MaRDI portal
Publication:2905305
DOI10.1142/S179383091250005XzbMath1253.68366MaRDI QIDQ2905305
Publication date: 27 August 2012
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Max-min weight balanced connected partition, Approximation algorithm for the balanced 2-connected \(k\)-partition problem, Uniform and most uniform partitions of trees
Cites Work
- Unnamed Item
- 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