Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-30
Computer Science
Data Structures and Algorithms
Scientific paper
10.1007/s10878-012-9481-z
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 $O(N\log N)$ time algorithm 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.
No associations
LandOfFree
Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-677957