Schnyder Greedy Routing Algorithm View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Xin He , Huaming Zhang

ABSTRACT

Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One major drawback of this approach is that the virtual coordinates requires Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications.In this paper, we introduce a modified version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance for routing decision, our routing algorithms use other criterion to determine routing path, solely based on local information. We present simple generalized greedy routing algorithms based on Schnyder coordinates (consisting of three integers between 0 and 2n), which are derived from Schnyder realizer for plane triangulations and Schnyder wood for 3-connected plane graphs. The algorithms are simple and can be easily implemented in linear time. More... »

PAGES

271-283

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_25

DOI

http://dx.doi.org/10.1007/978-3-642-13562-0_25

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1009749616


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA", 
          "id": "http://www.grid.ac/institutes/grid.265893.3", 
          "name": [
            "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Huaming", 
        "id": "sg:person.012041227127.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One major drawback of this approach is that the virtual coordinates requires \u03a9(nlogn) bits to represent, which makes this scheme infeasible in some applications.In this paper, we introduce a modified version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance for routing decision, our routing algorithms use other criterion to determine routing path, solely based on local information. We present simple generalized greedy routing algorithms based on Schnyder coordinates (consisting of three integers between 0 and 2n), which are derived from Schnyder realizer for plane triangulations and Schnyder wood for 3-connected plane graphs. The algorithms are simple and can be easily implemented in linear time.", 
    "editor": [
      {
        "familyName": "Kratochv\u00edl", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Angsheng", 
        "type": "Person"
      }, 
      {
        "familyName": "Fiala", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }, 
      {
        "familyName": "Kolman", 
        "givenName": "Petr", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13562-0_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13561-3", 
        "978-3-642-13562-0"
      ], 
      "name": "Theory and Applications of Models of Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "greedy routing algorithm", 
      "routing algorithm", 
      "greedy routing", 
      "network routing problem", 
      "geometric routing", 
      "virtual coordinates", 
      "virtual locations", 
      "local information", 
      "routing problem", 
      "Schnyder\u2019s realizers", 
      "routing", 
      "algorithm", 
      "linear time", 
      "elegant way", 
      "Schnyder woods", 
      "major drawback", 
      "graph", 
      "messages", 
      "bits", 
      "neighbors", 
      "scheme", 
      "plane triangulations", 
      "destination", 
      "drawbacks", 
      "information", 
      "coordinates", 
      "plane graph", 
      "realizers", 
      "triangulation", 
      "applications", 
      "path", 
      "simple form", 
      "version", 
      "decisions", 
      "way", 
      "location", 
      "distance", 
      "time", 
      "criteria", 
      "form", 
      "wood", 
      "paper", 
      "problem", 
      "approach", 
      "Schnyder coordinates", 
      "Schnyder Greedy Routing Algorithm"
    ], 
    "name": "Schnyder Greedy Routing Algorithm", 
    "pagination": "271-283", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009749616"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13562-0_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13562-0_25", 
      "https://app.dimensions.ai/details/publication/pub.1009749616"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_116.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13562-0_25"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_25'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_25'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13562-0_25'


 

This table displays all metadata directly associated to this object as RDF triples.

131 TRIPLES      23 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13562-0_25 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Ne962e859d9364d08bcd4d4eb35b70df4
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One major drawback of this approach is that the virtual coordinates requires Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications.In this paper, we introduce a modified version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance for routing decision, our routing algorithms use other criterion to determine routing path, solely based on local information. We present simple generalized greedy routing algorithms based on Schnyder coordinates (consisting of three integers between 0 and 2n), which are derived from Schnyder realizer for plane triangulations and Schnyder wood for 3-connected plane graphs. The algorithms are simple and can be easily implemented in linear time.
7 schema:editor N4f1077c79b6a47f78ab74217ec38b82f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd2f16d4729bc41a6ad75136f1eeedeec
12 schema:keywords Schnyder Greedy Routing Algorithm
13 Schnyder coordinates
14 Schnyder woods
15 Schnyder’s realizers
16 algorithm
17 applications
18 approach
19 bits
20 coordinates
21 criteria
22 decisions
23 destination
24 distance
25 drawbacks
26 elegant way
27 form
28 geometric routing
29 graph
30 greedy routing
31 greedy routing algorithm
32 information
33 linear time
34 local information
35 location
36 major drawback
37 messages
38 neighbors
39 network routing problem
40 paper
41 path
42 plane graph
43 plane triangulations
44 problem
45 realizers
46 routing
47 routing algorithm
48 routing problem
49 scheme
50 simple form
51 time
52 triangulation
53 version
54 virtual coordinates
55 virtual locations
56 way
57 wood
58 schema:name Schnyder Greedy Routing Algorithm
59 schema:pagination 271-283
60 schema:productId N6e87780cd5954b7e82b1e3c151d435a4
61 Nfd0227b4e1d3441c95b59f9ca8e8564a
62 schema:publisher N0f4b0e34f7494bea87aee7c836341398
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009749616
64 https://doi.org/10.1007/978-3-642-13562-0_25
65 schema:sdDatePublished 2021-11-01T18:46
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher N233a7386a862473d8f7d221ddb8c5dee
68 schema:url https://doi.org/10.1007/978-3-642-13562-0_25
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N0d3b7ccdcf354786becbb7f1b0847f14 schema:familyName Kolman
73 schema:givenName Petr
74 rdf:type schema:Person
75 N0f4b0e34f7494bea87aee7c836341398 schema:name Springer Nature
76 rdf:type schema:Organisation
77 N14b9d79a162f48dfbe6795060fa95c44 rdf:first N0d3b7ccdcf354786becbb7f1b0847f14
78 rdf:rest rdf:nil
79 N233a7386a862473d8f7d221ddb8c5dee schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N3e97db63e8854d8d8e2985eb47d9a350 schema:familyName Kratochvíl
82 schema:givenName Jan
83 rdf:type schema:Person
84 N4f1077c79b6a47f78ab74217ec38b82f rdf:first N3e97db63e8854d8d8e2985eb47d9a350
85 rdf:rest Nbcfc4aa6534746eaaac42bcfa0dab770
86 N5ffd8d05dc2149a39ec79250f25c15df schema:familyName Li
87 schema:givenName Angsheng
88 rdf:type schema:Person
89 N61eaffb96dfc436591cfa22ddd22e7f8 schema:familyName Fiala
90 schema:givenName Jiří
91 rdf:type schema:Person
92 N6c9c9a79526647fe9e85a272b376aaf2 rdf:first N61eaffb96dfc436591cfa22ddd22e7f8
93 rdf:rest N14b9d79a162f48dfbe6795060fa95c44
94 N6e87780cd5954b7e82b1e3c151d435a4 schema:name dimensions_id
95 schema:value pub.1009749616
96 rdf:type schema:PropertyValue
97 N7a8c2b4dc1db4d1fa845bb4cc3eb9227 rdf:first sg:person.012041227127.88
98 rdf:rest rdf:nil
99 Nbcfc4aa6534746eaaac42bcfa0dab770 rdf:first N5ffd8d05dc2149a39ec79250f25c15df
100 rdf:rest N6c9c9a79526647fe9e85a272b376aaf2
101 Nd2f16d4729bc41a6ad75136f1eeedeec schema:isbn 978-3-642-13561-3
102 978-3-642-13562-0
103 schema:name Theory and Applications of Models of Computation
104 rdf:type schema:Book
105 Ne962e859d9364d08bcd4d4eb35b70df4 rdf:first sg:person.011352641523.42
106 rdf:rest N7a8c2b4dc1db4d1fa845bb4cc3eb9227
107 Nfd0227b4e1d3441c95b59f9ca8e8564a schema:name doi
108 schema:value 10.1007/978-3-642-13562-0_25
109 rdf:type schema:PropertyValue
110 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
111 schema:name Information and Computing Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
114 schema:name Artificial Intelligence and Image Processing
115 rdf:type schema:DefinedTerm
116 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
117 schema:familyName He
118 schema:givenName Xin
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
120 rdf:type schema:Person
121 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
122 schema:familyName Zhang
123 schema:givenName Huaming
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
125 rdf:type schema:Person
126 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
127 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
128 rdf:type schema:Organization
129 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
130 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
131 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...