Three NP-Complete Optimization Problems in Seidel's Switching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00206094" target="_blank" >RIV/00216208:11320/08:00206094 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Three NP-Complete Optimization Problems in Seidel's Switching

Popis výsledku v původním jazyce

Annotation in the original language is: In this paper, we show the NP-completeness of the problem to determine if a given graph is switching-equivalent to a graph containing a clique whose size is at least a constant fraction of the graph size. We also prove the NP-completeness of deciding if a given graph is switching-equivalent to a graph having at least a given number of edges.

Název v anglickém jazyce

Three NP-Complete Optimization Problems in Seidel's Switching

Popis výsledku anglicky

Annotation in the original language is: In this paper, we show the NP-completeness of the problem to determine if a given graph is switching-equivalent to a graph containing a clique whose size is at least a constant fraction of the graph size. We also prove the NP-completeness of deciding if a given graph is switching-equivalent to a graph having at least a given number of edges.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

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

Proceedings of the International Workshop on Combinatorial Algorithms 2007

ISBN

9781904987673

ISSN

—

e-ISSN

—

Počet stran výsledku

15

Strana od-do

—

Název nakladatele

College Publications

Místo vydání

United Kingdom

Místo konání akce

United Kingdom

Datum konání akce

1. 1. 2008

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

WRD - Celosvětová akce

Kód UT WoS článku

—