Max-Tolerance graphs as intersection graphs: Cliques, cycles and recognition

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00003170" target="_blank" >RIV/00216208:11320/06:00003170 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Max-Tolerance graphs as intersection graphs: Cliques, cycles and recognition
Original language description
We show that max-tolerance graphs are intersection graphs of congruent triangles in the plane, and we exploit this representation to show that their recognition is NP-hard, but one can find a maximum clique in polynomial time.
Czech name
Max-toleranční grafy jako průnikové grafy: Klika, kružnice a rozpoznávání
Czech description
Ukazujeme, že max-toleranční grafy jsou průnikové grafy podobných trojúhelníků v rovině, a na základě této geometrické reprezentace dokazujeme, že jejich rozpoznáváníé je NP-těžké, ale maximální kliku lze nalézt v polynomálním čase.

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
0-89871-605-5
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
832-841
Publisher name
ACM - SIAM
Place of publication
New York - Philadelphia
Event location
New York - Philadelphia
Event date
Jan 1, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)