Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Recognition of Polygon-circle Graphs and Graphs of Interval Filaments is NP-complete
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph-theoretic Concepts in Computer Science
ISBN
978-3-540-74838-0
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
—
Publisher name
Springer
Place of publication
Berlin
Event location
Berlin
Event date
Jan 1, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000252884200023