Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Sandeep Bhadra , Afonso Ferreira

ABSTRACT

New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the topology of dynamic networks are hard to be effectively captured in a classical graph model. In this paper, we use evolving graphs, which helps capture the dynamic characteristics of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks. We first show that computing different types of strongly connected components in evolving digraphs is NP-Complete, and then propose an algorithm to build all rooted directed minimum spanning trees in strongly connected dynamic networks. More... »

PAGES

259-270

Book

TITLE

Ad-Hoc, Mobile, and Wireless Networks

ISBN

978-3-540-20260-8
978-3-540-39611-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-39611-6_23

DOI

http://dx.doi.org/10.1007/978-3-540-39611-6_23

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Madras", 
          "id": "https://www.grid.ac/institutes/grid.417969.4", 
          "name": [
            "Dept. of Electrical Engineering, Indian Institute of Technology, Madras, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhadra", 
        "givenName": "Sandeep", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "French National Centre for Scientific Research", 
          "id": "https://www.grid.ac/institutes/grid.4444.0", 
          "name": [
            "CNRS, I3S & INRIA-Sophia Antipolis, Projet Mascotte, BP93, 2004 Rt. des Lucioles, F-06902, Sophia Antipolis, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ferreira", 
        "givenName": "Afonso", 
        "id": "sg:person.014027376043.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014027376043.50"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-45749-6_53", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014883886", 
          "https://doi.org/10.1007/3-540-45749-6_53"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/381677.381683", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016680191"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/0471224561.ch22", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020126740"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45841-7_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037914310", 
          "https://doi.org/10.1007/3-540-45841-7_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45841-7_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037914310", 
          "https://doi.org/10.1007/3-540-45841-7_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230070103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038102583"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230040304", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038286095"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01919767", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052473839", 
          "https://doi.org/10.1007/bf01919767"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcom.1983.1095883", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061553713"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054103001728", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896465"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.17.3.395", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064727353"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.6.3.419", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064731725"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.2000.832223", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093181626"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.2000.832232", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093686176"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.2001.916310", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094083839"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/0471224561", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109698867"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109698867", 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the topology of dynamic networks are hard to be effectively captured in a classical graph model. In this paper, we use evolving graphs, which helps capture the dynamic characteristics of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks. We first show that computing different types of strongly connected components in evolving digraphs is NP-Complete, and then propose an algorithm to build all rooted directed minimum spanning trees in strongly connected dynamic networks.", 
    "editor": [
      {
        "familyName": "Pierre", 
        "givenName": "Samuel", 
        "type": "Person"
      }, 
      {
        "familyName": "Barbeau", 
        "givenName": "Michel", 
        "type": "Person"
      }, 
      {
        "familyName": "Kranakis", 
        "givenName": "Evangelos", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-39611-6_23", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-20260-8", 
        "978-3-540-39611-6"
      ], 
      "name": "Ad-Hoc, Mobile, and Wireless Networks", 
      "type": "Book"
    }, 
    "name": "Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks", 
    "pagination": "259-270", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049147060"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-39611-6_23"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ea20e0837a06014011f89189afaa8c717899b6bfb79427960fedd3699099dcf7"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-39611-6_23", 
      "https://app.dimensions.ai/details/publication/pub.1049147060"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29212_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-39611-6_23"
  }
]
 

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-540-39611-6_23'

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-540-39611-6_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39611-6_23'

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-540-39611-6_23'


 

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

134 TRIPLES      23 PREDICATES      43 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-39611-6_23 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N5e5fe0c4e8f84320a8ab6090df9fb4f5
4 schema:citation sg:pub.10.1007/3-540-45749-6_53
5 sg:pub.10.1007/3-540-45841-7_2
6 sg:pub.10.1007/bf01919767
7 https://app.dimensions.ai/details/publication/pub.1109698867
8 https://doi.org/10.1002/0471224561
9 https://doi.org/10.1002/0471224561.ch22
10 https://doi.org/10.1002/net.3230040304
11 https://doi.org/10.1002/net.3230070103
12 https://doi.org/10.1109/infcom.2000.832223
13 https://doi.org/10.1109/infcom.2000.832232
14 https://doi.org/10.1109/infcom.2001.916310
15 https://doi.org/10.1109/tcom.1983.1095883
16 https://doi.org/10.1142/s0129054103001728
17 https://doi.org/10.1145/381677.381683
18 https://doi.org/10.1287/opre.17.3.395
19 https://doi.org/10.1287/opre.6.3.419
20 schema:datePublished 2003
21 schema:datePublishedReg 2003-01-01
22 schema:description New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the topology of dynamic networks are hard to be effectively captured in a classical graph model. In this paper, we use evolving graphs, which helps capture the dynamic characteristics of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks. We first show that computing different types of strongly connected components in evolving digraphs is NP-Complete, and then propose an algorithm to build all rooted directed minimum spanning trees in strongly connected dynamic networks.
23 schema:editor Ndd5614869a084a5fb1dd34a5c0c6d7e4
24 schema:genre chapter
25 schema:inLanguage en
26 schema:isAccessibleForFree false
27 schema:isPartOf N1d6a7c751443415690023dab15830ea5
28 schema:name Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks
29 schema:pagination 259-270
30 schema:productId N235cdd72985c4a63ab0cf3b8f66e3909
31 Nb9a98e50b3f249a19f18b5f94bab590b
32 Nea2c2e77dfb04e41a399fbf57dbcb486
33 schema:publisher N38a72fce03f74ecaa520ae9fe7de8c1a
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049147060
35 https://doi.org/10.1007/978-3-540-39611-6_23
36 schema:sdDatePublished 2019-04-16T08:04
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N66c5b032298f4e8ea7c6e1649db2dc2e
39 schema:url https://link.springer.com/10.1007%2F978-3-540-39611-6_23
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N080a56addce34940a53283d9f55fc659 schema:familyName Kranakis
44 schema:givenName Evangelos
45 rdf:type schema:Person
46 N0f02427f538e4a02a3f5075f4726402f schema:affiliation https://www.grid.ac/institutes/grid.417969.4
47 schema:familyName Bhadra
48 schema:givenName Sandeep
49 rdf:type schema:Person
50 N1d6a7c751443415690023dab15830ea5 schema:isbn 978-3-540-20260-8
51 978-3-540-39611-6
52 schema:name Ad-Hoc, Mobile, and Wireless Networks
53 rdf:type schema:Book
54 N1e3794fe115f42c58d7c5348346b5adf rdf:first N446915bff1034af1b68e53e93ec305ac
55 rdf:rest Nc2fa85a259c94dfc97fc0649c4002bf3
56 N235cdd72985c4a63ab0cf3b8f66e3909 schema:name dimensions_id
57 schema:value pub.1049147060
58 rdf:type schema:PropertyValue
59 N38a72fce03f74ecaa520ae9fe7de8c1a schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 N446915bff1034af1b68e53e93ec305ac schema:familyName Barbeau
63 schema:givenName Michel
64 rdf:type schema:Person
65 N5e5fe0c4e8f84320a8ab6090df9fb4f5 rdf:first N0f02427f538e4a02a3f5075f4726402f
66 rdf:rest N9ba801b04191432f9ac17bc40aefca80
67 N66c5b032298f4e8ea7c6e1649db2dc2e schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N74c9058455184aedba85f6e03da934ea schema:familyName Pierre
70 schema:givenName Samuel
71 rdf:type schema:Person
72 N9ba801b04191432f9ac17bc40aefca80 rdf:first sg:person.014027376043.50
73 rdf:rest rdf:nil
74 Nb9a98e50b3f249a19f18b5f94bab590b schema:name doi
75 schema:value 10.1007/978-3-540-39611-6_23
76 rdf:type schema:PropertyValue
77 Nc2fa85a259c94dfc97fc0649c4002bf3 rdf:first N080a56addce34940a53283d9f55fc659
78 rdf:rest rdf:nil
79 Ndd5614869a084a5fb1dd34a5c0c6d7e4 rdf:first N74c9058455184aedba85f6e03da934ea
80 rdf:rest N1e3794fe115f42c58d7c5348346b5adf
81 Nea2c2e77dfb04e41a399fbf57dbcb486 schema:name readcube_id
82 schema:value ea20e0837a06014011f89189afaa8c717899b6bfb79427960fedd3699099dcf7
83 rdf:type schema:PropertyValue
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
88 schema:name Information Systems
89 rdf:type schema:DefinedTerm
90 sg:person.014027376043.50 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
91 schema:familyName Ferreira
92 schema:givenName Afonso
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014027376043.50
94 rdf:type schema:Person
95 sg:pub.10.1007/3-540-45749-6_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014883886
96 https://doi.org/10.1007/3-540-45749-6_53
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/3-540-45841-7_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037914310
99 https://doi.org/10.1007/3-540-45841-7_2
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/bf01919767 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052473839
102 https://doi.org/10.1007/bf01919767
103 rdf:type schema:CreativeWork
104 https://app.dimensions.ai/details/publication/pub.1109698867 schema:CreativeWork
105 https://doi.org/10.1002/0471224561 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109698867
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1002/0471224561.ch22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020126740
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1002/net.3230040304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038286095
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1002/net.3230070103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038102583
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1109/infcom.2000.832223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093181626
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/infcom.2000.832232 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093686176
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1109/infcom.2001.916310 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094083839
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1109/tcom.1983.1095883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061553713
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1142/s0129054103001728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896465
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1145/381677.381683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016680191
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1287/opre.17.3.395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727353
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1287/opre.6.3.419 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064731725
128 rdf:type schema:CreativeWork
129 https://www.grid.ac/institutes/grid.417969.4 schema:alternateName Indian Institute of Technology Madras
130 schema:name Dept. of Electrical Engineering, Indian Institute of Technology, Madras, Chennai, India
131 rdf:type schema:Organization
132 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
133 schema:name CNRS, I3S & INRIA-Sophia Antipolis, Projet Mascotte, BP93, 2004 Rt. des Lucioles, F-06902, Sophia Antipolis, France
134 rdf:type schema:Organization
 




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


...