Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
type: Item
instance of: scholarly article
title: Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
author: Xiaofei Liu
author: Ya-jie Li
author: Weidong Li
author: Jin-Hua Yang
published in: Journal of Combinatorial Optimization
publication date: 2023-01-17T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7642707
zbMATH Keywords: connected bipartition problem
zbMATH Keywords: grid graph
zbMATH Keywords: interval graph
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: s10878-022-00981-9
OpenAlex ID: W4313826142
cites work: Max-min partitioning of grid graphs into connected components
cites work: A polynomial-time algorithm for max-min partitioning of ladders
cites work: Shifting algorithms for tree partitioning with general weighting functions
cites work: Q5387695
cites work: Approximation algorithms for the maximally balanced connected graph tripartition problem
cites work: Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date
cites work: Approximation algorithms for maximally balanced connected graph partition
cites work: Approximating the Maximally Balanced Connected Partition Problem in graphs
cites work: A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work
cites work: Computing an st-numbering
cites work: Q4198056
cites work: Bounds for Certain Multiprocessing Anomalies
cites work: A common approximation framework for early work, late work, and resource leveling problems
cites work: Q5596083
cites work: Approximation algorithms for the maximum bounded connected bipartition problem
cites work: Most uniform path partitioning and its use in image processing
cites work: Doubly Balanced Connected Graph Partitioning
cites work: Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
cites work: A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs
cites work: Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
cites work: Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
cites work: A heuristic algorithm for the mini-max spanning forest problem
cites work: Semi-online early work maximization problem on two hierarchical machines with partial information of processing time
cites work: Online early work maximization problem on two hierarchical machines with buffer or rearrangements
DOI: 10.1007/S10878-022-00981-9
description: scientific article; zbMATH DE number 7642707