Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

28 March 2024
 
  » arxiv » 1306.6593

 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
AbstractWe 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica