Complexity of hypergraph coloring and Seidel's switching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F03%3A00002033" target="_blank" >RIV/00216208:11320/03:00002033 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity of hypergraph coloring and Seidel's switching

Popis výsledku v původním jazyce

It is proved that deciding if a given graph is switchig equivalent to a regular graph is NP-complete. The proof is based on a variant of regular hypergraph bicoloring problem.

Název v anglickém jazyce

Complexity of hypergraph coloring and Seidel's switching

Popis výsledku anglicky

It is proved that deciding if a given graph is switchig equivalent to a regular graph is NP-complete. The proof is based on a variant of regular hypergraph bicoloring problem.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/LN00A056" target="_blank" >LN00A056: Institut teoretické informatiky - Centrum mladé vědy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2003

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

Graph Theoretic Concepts in Computer Science

ISBN

3-540-20452-0

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

297-308

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Berlin

Datum konání akce

1. 1. 2003

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

WRD - Celosvětová akce

Kód UT WoS článku

—