NDA
Bejelentkezés
Kapcsolat
Blocking optimal k-arborescences |
Tartalom: | http://real.mtak.hu/28215/ |
---|---|
Archívum: | MTA Könyvtár |
Gyűjtemény: |
Status = Submitted
Type = Conference or Workshop Item |
Cím: |
Blocking optimal k-arborescences
|
Létrehozó: |
Bernáth, Attila
Király, Tamás
|
Dátum: |
2015-07-08
|
Téma: |
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
|
Tartalmi leírás: |
Given a digraph $D=(V,A)$ and a positive integer $k$, an arc set $Fsubseteq A$ is called a $k$-arborescence if it is the disjoint union of $k$ spanning arborescences. The problem of finding a minimum cost $k$-arborescence is known to be polynomial-time solvable using matroid intersection. In this paper we study the following problem: find a minimum cardinality subset of arcs that contains at least one arc from every minimum cost $k$-arborescence. For $k=1$, the problem was solved in [A. Bernáth, G. Pap , Blocking optimal arborescences, IPCO 2013]. In this paper we give an algorithm for general $k$ that has polynomial running time if $k$ is fixed.
|
Típus: |
Conference or Workshop Item
NonPeerReviewed
|
Formátum: |
text
|
Azonosító: |
Bernáth, Attila and Király, Tamás (2015) Blocking optimal k-arborescences. In: ACM-SIAM Symposium on Discrete Algorithms (SODA16), 10-12 January 2016, Arlington, Virginia, USA. (Submitted)
|
Kapcsolat: |