On the Simultaneous Minimum Spanning Trees Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385823" target="_blank" >RIV/00216208:11320/18:10385823 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-319-74180-2_20" target="_blank" >https://doi.org/10.1007/978-3-319-74180-2_20</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-74180-2_20" target="_blank" >10.1007/978-3-319-74180-2_20</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Simultaneous Minimum Spanning Trees Problem

Popis výsledku v původním jazyce

Simultaneous Embedding with Fixed Edges (SEFE) [1] is a problem where given k planar graphs we ask whether they can be simultaneously embedded so that the embedding of each graph is planar and common edges are drawn the same. Problems of SEFE type have inspired questions of Simultaneous Geometrical Representations and further derivations. Based on this motivation we investigate the generalization of the simultaneous paradigm on the classical combinatorial problem of minimum spanning trees. Given k graphs with weighted edges, such that they have a common intersection, are there minimum spanning trees of the respective graphs such that they agree on the intersection? We show that the unweighted case is polynomial-time solvable while the weighted case is only polynomial-time solvable for

Název v anglickém jazyce

On the Simultaneous Minimum Spanning Trees Problem

Popis výsledku anglicky

Simultaneous Embedding with Fixed Edges (SEFE) [1] is a problem where given k planar graphs we ask whether they can be simultaneously embedded so that the embedding of each graph is planar and common edges are drawn the same. Problems of SEFE type have inspired questions of Simultaneous Geometrical Representations and further derivations. Based on this motivation we investigate the generalization of the simultaneous paradigm on the classical combinatorial problem of minimum spanning trees. Given k graphs with weighted edges, such that they have a common intersection, are there minimum spanning trees of the respective graphs such that they agree on the intersection? We show that the unweighted case is polynomial-time solvable while the weighted case is only polynomial-time solvable for

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings

ISBN

978-3-319-74179-6

ISSN

0302-9743

e-ISSN

neuvedeno

Počet stran výsledku

14

Strana od-do

235-248

Název nakladatele

Springer

Místo vydání

India

Místo konání akce

Guwahati, India

Datum konání akce

15. 2. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—