On the Simultaneous Minimum Spanning Trees Problem

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

On the Simultaneous Minimum Spanning Trees Problem

Original language description

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

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

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

Publication year

2018

Confidentiality

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

Article name in the collection

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

Number of pages

14

Pages from-to

235-248

Publisher name

Springer

Place of publication

India

Event location

Guwahati, India

Event date

Feb 15, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—