About: On the Computational Complexity of Degenerate Unit Distance Representations of Graphs     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

AttributesValues
rdf:type
rdfs:seeAlso
Description
  • 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 embaldings has been studied before. We initiate the study of the computational complexity of (possibly) degenerate embeddings. In particular we prove that for every k }= 2, deciding if an input graph has a (possibly) degenerate k-dimensional unit distance representation is NP-hard.
  • 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 embaldings has been studied before. We initiate the study of the computational complexity of (possibly) degenerate embeddings. In particular we prove that for every k }= 2, deciding if an input graph has a (possibly) degenerate k-dimensional unit distance representation is NP-hard. (en)
Title
  • On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
  • On the Computational Complexity of Degenerate Unit Distance Representations of Graphs (en)
skos:prefLabel
  • On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
  • On the Computational Complexity of Degenerate Unit Distance Representations of Graphs (en)
skos:notation
  • RIV/00216208:11320/11:10100204!RIV12-MSM-11320___
http://linked.open...avai/predkladatel
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • P(1M0545), Z(MSM0021620838)
http://linked.open...vai/riv/dodaniDat
http://linked.open...aciTvurceVysledku
http://linked.open.../riv/druhVysledku
http://linked.open...iv/duvernostUdaju
http://linked.open...titaPredkladatele
http://linked.open...dnocenehoVysledku
  • 218184
http://linked.open...ai/riv/idVysledku
  • RIV/00216208:11320/11:10100204
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • Graph; Representation; Computational Complexity (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...ontrolniKodProRIV
  • [0855D4AE8190]
http://linked.open...v/mistoKonaniAkce
  • Londýn
http://linked.open...i/riv/mistoVydani
  • Berlin
http://linked.open...i/riv/nazevZdroje
  • COMBINATORIAL ALGORITHMS
http://linked.open...in/vavai/riv/obor
http://linked.open...ichTvurcuVysledku
http://linked.open...cetTvurcuVysledku
http://linked.open...vavai/riv/projekt
http://linked.open...UplatneniVysledku
http://linked.open...iv/tvurceVysledku
  • Kratochvíl, Jan
  • Horvat, Boris
  • Pisanski, Tomaz
http://linked.open...vavai/riv/typAkce
http://linked.open...ain/vavai/riv/wos
  • 000290418700028
http://linked.open.../riv/zahajeniAkce
http://linked.open...n/vavai/riv/zamer
issn
  • 0302-9743
number of pages
http://bibframe.org/vocab/doi
  • 10.1007/978-3-642-19222-7_28
http://purl.org/ne...btex#hasPublisher
  • SPRINGER
https://schema.org/isbn
  • 978-3-642-19221-0
http://localhost/t...ganizacniJednotka
  • 11320
is http://linked.open...avai/riv/vysledek of
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 41 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software