Greedy Routing via Embedding Graphs onto Semi-metric Spaces View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Huaming Zhang , Swetha Govindaiah

ABSTRACT

In this paper, we generalize the greedy routing concept to use semi-metric spaces. We prove that any connected n-vertex graph G admits a greedy embedding onto an appropriate semi-metric space such that (1) each vertex v of the graph is represented by up to k virtual coordinates (where the numbers are from 1 to 2n − 1 and k ≤ deg(v)); and (2) using an appropriate distance definition, there is always a distance decreasing path between any two vertices in G. In particular, we prove that, for a 3-connected plane graph G, there is a greedy embedding of G such that: (1) the greedy embedding can be obtained in linear time; and (2) each vertex can be represented by at most 3 virtual coordinates from 1 to 2n − 1. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in O(logn) bits. More... »

PAGES

58-69

Book

TITLE

Frontiers in Algorithmics and Algorithmic Aspects in Information and Management

ISBN

978-3-642-21203-1
978-3-642-21204-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-21204-8_10

DOI

http://dx.doi.org/10.1007/978-3-642-21204-8_10

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "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"
      }, 
      {
        "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": "Govindaiah", 
        "givenName": "Swetha", 
        "id": "sg:person.016541127375.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016541127375.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "In this paper, we generalize the greedy routing concept to use semi-metric spaces. We prove that any connected n-vertex graph G admits a greedy embedding onto an appropriate semi-metric space such that (1) each vertex v of the graph is represented by up to k virtual coordinates (where the numbers are from 1 to 2n\u2009\u2212\u20091 and k\u2009\u2264\u2009deg(v)); and (2) using an appropriate distance definition, there is always a distance decreasing path between any two vertices in G. In particular, we prove that, for a 3-connected plane graph G, there is a greedy embedding of G such that: (1) the greedy embedding can be obtained in linear time; and (2) each vertex can be represented by at most 3 virtual coordinates from 1 to 2n\u2009\u2212\u20091. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in O(logn) bits.", 
    "editor": [
      {
        "familyName": "Atallah", 
        "givenName": "Mikhail", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Xiang-Yang", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Binhai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-21204-8_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-21203-1", 
        "978-3-642-21204-8"
      ], 
      "name": "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management", 
      "type": "Book"
    }, 
    "keywords": [
      "semi-metric space", 
      "greedy embedding", 
      "graph G", 
      "linear time", 
      "vertex graph G", 
      "plane graph G", 
      "non-standard notion", 
      "plane graph", 
      "vertex v", 
      "greedy routing", 
      "vertices", 
      "graph", 
      "virtual coordinates", 
      "coordinates", 
      "distance definition", 
      "space", 
      "embedding", 
      "greedy routing algorithm", 
      "routing algorithm", 
      "algorithm", 
      "routing concept", 
      "routing", 
      "path", 
      "notion", 
      "distance", 
      "time", 
      "definition", 
      "bits", 
      "concept", 
      "better knowledge", 
      "knowledge", 
      "paper"
    ], 
    "name": "Greedy Routing via Embedding Graphs onto Semi-metric Spaces", 
    "pagination": "58-69", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047430319"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-21204-8_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-21204-8_10", 
      "https://app.dimensions.ai/details/publication/pub.1047430319"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:49", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_64.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-21204-8_10"
  }
]
 

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-21204-8_10'

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-21204-8_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21204-8_10'

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-21204-8_10'


 

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

109 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-21204-8_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncdda833427794457965eb63fa7585d64
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description In this paper, we generalize the greedy routing concept to use semi-metric spaces. We prove that any connected n-vertex graph G admits a greedy embedding onto an appropriate semi-metric space such that (1) each vertex v of the graph is represented by up to k virtual coordinates (where the numbers are from 1 to 2n − 1 and k ≤ deg(v)); and (2) using an appropriate distance definition, there is always a distance decreasing path between any two vertices in G. In particular, we prove that, for a 3-connected plane graph G, there is a greedy embedding of G such that: (1) the greedy embedding can be obtained in linear time; and (2) each vertex can be represented by at most 3 virtual coordinates from 1 to 2n − 1. To our best knowledge, this is the first greedy routing algorithm for 3-connected plane graphs, albeit with non-standard notions of greedy embedding and greedy routing, such that: (1) it runs in linear time to compute the virtual coordinates for the vertices; and (2) the virtual coordinates are represented succinctly in O(logn) bits.
7 schema:editor N6f6834b42f1b4f9594bf7cae84d31b34
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5fa87185ff5f4c4c9340be27086e5b22
12 schema:keywords algorithm
13 better knowledge
14 bits
15 concept
16 coordinates
17 definition
18 distance
19 distance definition
20 embedding
21 graph
22 graph G
23 greedy embedding
24 greedy routing
25 greedy routing algorithm
26 knowledge
27 linear time
28 non-standard notion
29 notion
30 paper
31 path
32 plane graph
33 plane graph G
34 routing
35 routing algorithm
36 routing concept
37 semi-metric space
38 space
39 time
40 vertex graph G
41 vertex v
42 vertices
43 virtual coordinates
44 schema:name Greedy Routing via Embedding Graphs onto Semi-metric Spaces
45 schema:pagination 58-69
46 schema:productId N833b17ed912c46c0912cd5b4c1e42499
47 Ne86590ba5c89416694393d6bba8acf07
48 schema:publisher N4186a4d698be42d09228f4970e5df2b4
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047430319
50 https://doi.org/10.1007/978-3-642-21204-8_10
51 schema:sdDatePublished 2022-05-20T07:49
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N0f97f4b195164b8db798f6a93d25352e
54 schema:url https://doi.org/10.1007/978-3-642-21204-8_10
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N0ba9638d66b84813a88910a0c01b7b07 schema:familyName Atallah
59 schema:givenName Mikhail
60 rdf:type schema:Person
61 N0f97f4b195164b8db798f6a93d25352e schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N135dc73ea45242048d1a901cb2e960e0 rdf:first sg:person.016541127375.33
64 rdf:rest rdf:nil
65 N2835b678a6644da8a279a60e613d0465 rdf:first Nf0d936bed697438c98c048d5b49eff8c
66 rdf:rest rdf:nil
67 N4186a4d698be42d09228f4970e5df2b4 schema:name Springer Nature
68 rdf:type schema:Organisation
69 N5fa87185ff5f4c4c9340be27086e5b22 schema:isbn 978-3-642-21203-1
70 978-3-642-21204-8
71 schema:name Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
72 rdf:type schema:Book
73 N6f6834b42f1b4f9594bf7cae84d31b34 rdf:first N0ba9638d66b84813a88910a0c01b7b07
74 rdf:rest N77cf3018215f42d4ac4a0b6b24b2af08
75 N77cf3018215f42d4ac4a0b6b24b2af08 rdf:first N97284a81c2474aeabd836741512be315
76 rdf:rest N2835b678a6644da8a279a60e613d0465
77 N833b17ed912c46c0912cd5b4c1e42499 schema:name doi
78 schema:value 10.1007/978-3-642-21204-8_10
79 rdf:type schema:PropertyValue
80 N97284a81c2474aeabd836741512be315 schema:familyName Li
81 schema:givenName Xiang-Yang
82 rdf:type schema:Person
83 Ncdda833427794457965eb63fa7585d64 rdf:first sg:person.012041227127.88
84 rdf:rest N135dc73ea45242048d1a901cb2e960e0
85 Ne86590ba5c89416694393d6bba8acf07 schema:name dimensions_id
86 schema:value pub.1047430319
87 rdf:type schema:PropertyValue
88 Nf0d936bed697438c98c048d5b49eff8c schema:familyName Zhu
89 schema:givenName Binhai
90 rdf:type schema:Person
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
98 schema:familyName Zhang
99 schema:givenName Huaming
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
101 rdf:type schema:Person
102 sg:person.016541127375.33 schema:affiliation grid-institutes:grid.265893.3
103 schema:familyName Govindaiah
104 schema:givenName Swetha
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016541127375.33
106 rdf:type schema:Person
107 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
108 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
109 rdf:type schema:Organization
 




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


...