| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs | Marcin Pilipczuk
; Michał Pilipczuk
; Piotr Sankowski
; Erik Jan van Leeuwen
; | Date: |
27 Jun 2013 | Abstract: | We propose polynomial-time algorithms that sparsify planar and bounded-genus
graphs while preserving optimal solutions to Steiner problems. Our main
contribution is a polynomial-time algorithm that, given a graph G embedded on a
surface of genus g and a designated face f bounded by a simple cycle of length
k, uncovers a set F in E(G) of size polynomial in g and k that contains an
optimal Steiner tree for any set of terminals that is a subset of the vertices
of f.
We apply this general theorem to prove that: * given a graph G embedded on a
surface of genus g and a terminal set S in V(G), one can in polynomial time
find a set F in E(G) that contains an optimal Steiner tree T for S and that has
size polynomial in g and |E(T)|; * an analogous result holds for the Steiner
Forest problem; * given a planar graph G and a terminal set S in V(G), one can
in polynomial time find a set F in E(G) that contains an optimal edge multiway
cut C separating S (i.e., a cutset that intersects any path with endpoints in
different terminals from S) and that has size polynomial in |C|.
In the language of parameterized complexity, these results imply the first
polynomial kernels for Steiner Tree and Steiner Forest on planar and bounded
genus graphs (parameterized by the size of the tree and forest, respectively)
and for the edge-deletion variant of Multiway Cut on planar graphs
(parameterized by the size of the cutset). | Source: | arXiv, 1306.6593 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |