Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

DOI10.1007/s10878-022-00981-9OpenAlexW4313826142MaRDI QIDQ2111532

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

Publication date: 17 January 2023

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00981-9

zbMATH Keywords

approximation algorithminterval graphgrid graphconnected bipartition problem

Mathematics Subject Classification ID

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

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
• Computing an st-numbering
• A heuristic algorithm for the mini-max spanning forest problem
• 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
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Approximation algorithms for the maximum bounded connected bipartition problem
• Semi-online early work maximization problem on two hierarchical machines with partial information of processing time
• 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
• Online early work maximization problem on two hierarchical machines with buffer or rearrangements

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