Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs

DOI10.1007/S10878-012-9481-ZzbMath1282.90223arXiv1105.5915OpenAlexW1557249042MaRDI QIDQ385485

Bang Ye Wu

Publication date: 2 December 2013

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

Full work available at URL: https://arxiv.org/abs/1105.5915

zbMATH Keywords

approximation algorithmgrid graphsbalanced connected partitionnon-separating path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (2)

Approximation algorithms for the maximum bounded connected bipartition problem ⋮ Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

Cites Work

• Unnamed Item
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• A weaker version of Lovász' path removal conjecture
• Computing an st-numbering
• Non-separating paths in 4-connected graphs
• Graph connectivity after path removal
• Highly linked graphs
• Max-Min Tree Partitioning
• A homology theory for spanning tress of a graph
• Max-min partitioning of grid graphs into connected components
• Fibonacci heaps and their uses in improved network optimization algorithms
• Lowest common ancestors in trees and directed acyclic graphs
• A polynomial-time algorithm for max-min partitioning of ladders

This page was built for publication: Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs