Approximation algorithms for the maximum bounded connected bipartition problem

DOI10.1007/978-3-030-93176-6_3zbMath1498.68210OpenAlexW4205619114MaRDI QIDQ2151359

Ya-jie Li, Xiaofei Liu, Weidong Li, Jin-Hua Yang

Publication date: 1 July 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-93176-6_3

zbMATH Keywords

approximation algorithminterval graphFPTASconnected bipartition problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (1)

Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Balanced connected graph partition
• On the complexity of partitioning graphs into connected subgraphs
• Computing an st-numbering
• Clustering on trees
• Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
• Most uniform path partitioning and its use in image processing
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Mirror scheduling problems with early work and late work criteria
• A common approximation framework for early work, late work, and resource leveling problems
• Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date
• 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
• Shifting algorithms for tree partitioning with general weighting functions
• Max-min partitioning of grid graphs into connected components
• Doubly Balanced Connected Graph Partitioning
• A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work
• Bounds for Certain Multiprocessing Anomalies
• Approximation algorithms for maximally balanced connected graph partition
• A polynomial-time algorithm for max-min partitioning of ladders

This page was built for publication: Approximation algorithms for the maximum bounded connected bipartition problem