Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
From MaRDI portal
Publication:385485
DOI10.1007/s10878-012-9481-zzbMath1282.90223arXiv1105.5915OpenAlexW1557249042MaRDI QIDQ385485
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
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
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