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

DOI10.1007/S10878-012-9481-ZzbMATH Open1282.90223arXiv1105.5915OpenAlexW1557249042MaRDI QIDQ385485FDOQ385485

Authors: Bang Ye Wu 

Publication date: 2 December 2013

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

Abstract: For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP${}_2$) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time $O(NlogN)$ for finding a minimum weight non-separating path between two given nodes in a grid graph of $N$ nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP${}_2$ problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP${}_2$ problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows.

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

Recommendations

• A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs
• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Max-min partitioning of grid graphs into connected components
• Approximation algorithm for the balanced 2-connected bipartition problem
• The bisection width of grid graphs

zbMATH Keywords

approximation algorithmgrid graphsbalanced connected partitionnon-separating path

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Combinatorial 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 algorithms for the maximum bounded connected bipartition problem
• The bisection width of grid graphs

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

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