About: Approximating the Crossing Number of Toroidal 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
Description
  • CrossingNumber is one of the most challenging algorithmic problems in topological graph theory, with applications to graph drawing and VLSI layout. No polynomial time constant approximation algorithm is known for this NP-complete problem. We prove that a natural approach to planar drawing of toroidal graphs (used already by Pach and T\'oth) gives a polynomial time constant approximation algorithm for the crossing number of toroidal graphs with bounded degree. In this proof we present a new ``grid'' theorem on toroidal graphs.
  • CrossingNumber is one of the most challenging algorithmic problems in topological graph theory, with applications to graph drawing and VLSI layout. No polynomial time constant approximation algorithm is known for this NP-complete problem. We prove that a natural approach to planar drawing of toroidal graphs (used already by Pach and T\'oth) gives a polynomial time constant approximation algorithm for the crossing number of toroidal graphs with bounded degree. In this proof we present a new ``grid'' theorem on toroidal graphs. (en)
Title
  • Approximating the Crossing Number of Toroidal Graphs
  • Approximating the Crossing Number of Toroidal Graphs (en)
skos:prefLabel
  • Approximating the Crossing Number of Toroidal Graphs
  • Approximating the Crossing Number of Toroidal Graphs (en)
skos:notation
  • RIV/00216224:14330/07:00020423!RIV10-GA0-14330___
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • P(GA201/05/0050)
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
  • 410603
http://linked.open...ai/riv/idVysledku
  • RIV/00216224:14330/07:00020423
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • crossing number; crossing minimization; approximation (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...ontrolniKodProRIV
  • [38EED1E0CBB1]
http://linked.open...v/mistoKonaniAkce
  • Sendai, Japan
http://linked.open...i/riv/mistoVydani
  • Berlin
http://linked.open...i/riv/nazevZdroje
  • International Symposium on Algorithms and Computation (ISAAC 2007)
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
  • Hliněný, Petr
  • Salazar, Gelasio
http://linked.open...vavai/riv/typAkce
http://linked.open.../riv/zahajeniAkce
number of pages
http://purl.org/ne...btex#hasPublisher
  • Springer-Verlag
https://schema.org/isbn
  • 978-3-540-77118-0
http://localhost/t...ganizacniJednotka
  • 14330
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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software