|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Dynamic Steiner Tree in Planar Graphs | | Jakub Łcacki
; Jakub Oćwieja
; Marcin Pilipczuk
; Piotr Sankowski
; Anna Zych
; | | Date: |
15 Aug 2013 | | Abstract: | In this paper we study the Steiner tree problem over a dynamic set of
terminals. We consider the model where we are given an $n$-vertex graph
$G=(V,E,w)$ with nonnegative edge weights. Our goal is to maintain a tree $T$
which is a good approximation of the minimum Steiner tree in $G$ when the
terminal set $S subseteq V$ changes over time. The changes applied to the
terminal set are either terminal additions (emph{incremental} scenario),
terminal removals (emph{decremental} scenario), or both ({em fully dynamic}
scenario). We obtain the first known sublinear time algorithm for dynamic
Steiner tree problem in planar graphs. In particular we develop a
polylogarithmic time incremental algorithm, an $igo(sqrt{n} log^{2.5} n
log strecz)$ time decremental algorithm and an $igo(sqrt{n} log^{5} n
log strecz)$ %and $igo(n^{1/2+delta})$ time fully-dynamic algorithm. | | Source: | arXiv, 1308.3336 | | 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 Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER