Approximation algorithms for the maximum bounded connected bipartition problem

DOI10.1007/978-3-030-93176-6_3MaRDI QIDQ2151359zbMATH OpenOpenAlexFDO

Authors Ya-jie Li, Weidong Li, Xiaofei Liu, 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 algorithmFPTASinterval graphconnected bipartition problem

Mathematics Subject Classification ID

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

Recommendations

• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Approximation algorithm for the balanced 2-connected bipartition problem
• Approximation algorithm for the balanced 2-connected k-partition problem
• Approximation and inaproximability results on balanced connected partitions of graphs
• Approximating the Maximally Balanced Connected Partition Problem in graphs

Cites work

• scientific article; zbMATH DE number 432817 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs
• A common approximation framework for early work, late work, and resource leveling problems
• A parallel machine scheduling problem maximizing total weighted early work
• A polynomial-time algorithm for max-min partitioning of ladders
• 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
• Approximation algorithms for maximally balanced connected graph partition
• Approximation and inaproximability results on balanced connected partitions of graphs
• Balanced connected graph partition
• Bounds for Certain Multiprocessing Anomalies
• Clustering on trees
• Computing an st-numbering
• 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
• Max-min partitioning of grid graphs into connected components
• Mirror scheduling problems with early work and late work criteria
• Most uniform path partitioning and its use in image processing
• On the complexity of partitioning graphs into connected subgraphs
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
• Shifting algorithms for tree partitioning with general weighting functions

Cited in

(9)

• Approximation and parameterized algorithms for balanced connected partition problems
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Approximation algorithm for the balanced 2-connected \(k\)-partition problem
• Approximation algorithm for the balanced 2-connected bipartition problem
• An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
• scientific article; zbMATH DE number 6288786 (Why is no real title available?)
• Approximation algorithms for maximally balanced connected graph partition

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

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