Computational Complexity of Covering Three-Vertex Multigraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10282429" target="_blank" >RIV/00216208:11320/14:10282429 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-662-44465-8_42" target="_blank" >http://dx.doi.org/10.1007/978-3-662-44465-8_42</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-44465-8_42" target="_blank" >10.1007/978-3-662-44465-8_42</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computational Complexity of Covering Three-Vertex Multigraphs

Popis výsledku v původním jazyce

A covering projection from a graph G to a graph H is a mapping of the vertices of G to the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively to the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetricgraphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of decidingthe existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown to be NP-hard for simple regular graphs H of valency greater than 2, and a full characterizati

Název v anglickém jazyce

Computational Complexity of Covering Three-Vertex Multigraphs

Popis výsledku anglicky

A covering projection from a graph G to a graph H is a mapping of the vertices of G to the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively to the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetricgraphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of decidingthe existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown to be NP-hard for simple regular graphs H of valency greater than 2, and a full characterizati

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

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í

2014

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

Mathematical Foundations of Computer Science 2014

ISBN

978-3-662-44464-1

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

493-504

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Budapest

Datum konání akce

25. 8. 2014

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

WRD - Celosvětová akce

Kód UT WoS článku

—