Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

DOI10.1007/S10878-022-00981-9OpenAlexW4313826142MaRDI QIDQ2111532FDOQ2111532

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

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

• Title not available (Why is that?)
• Most uniform path partitioning and its use in image processing
• Title not available (Why is that?)
• Bounds for Certain Multiprocessing Anomalies
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs
• A heuristic algorithm for the mini-max spanning forest problem
• Computing an st-numbering
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
• Max-min partitioning of grid graphs into connected components
• A polynomial-time algorithm for max-min partitioning of ladders
• Title not available (Why is that?)
• Approximation algorithms for maximally balanced connected graph partition
• Shifting algorithms for tree partitioning with general weighting functions
• Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
• Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Approximation algorithms for the maximum bounded connected bipartition problem
• Doubly Balanced Connected Graph Partitioning
• 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
• A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work
• Online early work maximization problem on two hierarchical machines with buffer or rearrangements

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem

   Recommendations

• Approximation algorithms for the maximum bounded connected bipartition problem 👍 👎
• A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs 👍 👎
• Approximation algorithm for the balanced 2-connected bipartition problem 👍 👎
• Approximating the Maximally Balanced Connected Partition Problem in graphs 👍 👎
• Approximation algorithms for maximally balanced connected graph partition 👍 👎

This page was built for publication: Combinatorial 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 Q2111532)