-
On the computational complexity of degenerate unit distance representations of graphsHorvat, Boris, 1976- ; Kratochvíl, Jan ; Pisanski, TomažSome graphs admit drawings in the Euclidean ▫$k$▫-space in such a (natural) way,that edges are represented as line segments of unit length. Such embeddings are called ▫$k$▫-dimensional unit distance ... representations. The embedding is strict if the distances of points representing nonadjacent pairs of vertices are different than 1. When two non-adjacent vertices are drawn in the same point, we say that the representation is degenerate. Computational complexity of nondegenerate embeddings has been studied before. We initiate the study of the computational complexity of (possibly) degenerate embeddings. In particular we prove that for every ▫$k \ge 2$▫, deciding if an input graph has a (possibly) degenerate ▫$k$▫-dimensional unit distance representation is NP-hard.Vir: Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010 : revised selected papers (Str. 274-285)Vrsta gradiva - prispevek na konferenciLeto - 2011Jezik - angleškiCOBISS.SI-ID - 15878745
Avtor
Horvat, Boris, 1976- |
Kratochvíl, Jan |
Pisanski, Tomaž
Teme
matematika |
teorija grafov |
grafi z enotsko razdaljo |
dimenzija grafa |
evklidska dimenzija grafa |
degenerirana reprezentacija |
računska zahtevnost |
mathematics |
graph theory |
unit distance graph |
dimension of a graph |
Euclidean dimension of a graph |
degenerate representation |
complexity
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Horvat, Boris, 1976- | 24421 |
Kratochvíl, Jan | |
Pisanski, Tomaž | 01941 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.