On Hardness of the Joint Crossing Number

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00081412" target="_blank" >RIV/00216224:14330/15:00081412 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-662-48971-0_51" target="_blank" >http://dx.doi.org/10.1007/978-3-662-48971-0_51</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-48971-0_51" target="_blank" >10.1007/978-3-662-48971-0_51</a>

Jazyk výsledku
angličtina
Název v původním jazyce
On Hardness of the Joint Crossing Number
Popis výsledku v původním jazyce
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction froma special variant of the anchored crossing number problem of Cabello and Mohar.
Název v anglickém jazyce
On Hardness of the Joint Crossing Number
Popis výsledku anglicky
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction froma special variant of the anchored crossing number problem of Cabello and Mohar.

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í
2015
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
International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472
ISBN
9783662489703
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
11
Strana od-do
603-613
Název nakladatele
Springer Verlag
Místo vydání
Berlin
Místo konání akce
Nagoya, Japan
Datum konání akce
9. 12. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)