Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00206176" target="_blank" >RIV/00216208:11320/07:00206176 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete

Popis výsledku v původním jazyce

We provide a polynomial reduction showing NP=completeness for the recognition problem of intersection graphs of convex polygons inscribed in the circle (Polygon=circle graphs) and as well for class of intersection graphs of filaments above intervals on aline. Moreover we show that between these two classes no polynomially recognizable class can be sandwiched.

Název v anglickém jazyce

Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete

Popis výsledku anglicky

We provide a polynomial reduction showing NP=completeness for the recognition problem of intersection graphs of convex polygons inscribed in the circle (Polygon=circle graphs) and as well for class of intersection graphs of filaments above intervals on aline. Moreover we show that between these two classes no polynomially recognizable class can be sandwiched.

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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

978-3-540-74838-0

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

—

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Berlin

Datum konání akce

1. 1. 2007

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

WRD - Celosvětová akce

Kód UT WoS článku

000252884200023