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 N4cc98741fe8948f59909b5bad94a58de
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 Nece95357829442a4a74b09372ef99541
24 schema:genre chapter
25 schema:inLanguage en
26 schema:isAccessibleForFree false
27 schema:isPartOf N6b20a00677c74c73981203f98f952566
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 N1d97a685edef4bc4808a39646ab9e49c
31 N30d2666f92f040eda422f387689d2bfa
32 Nad41cfc9abff4ba7aeeff1ae4eadba37
33 schema:publisher Nb4234109372c49578eab9469d5bab7c0
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 Nbf7baeaae45343479b91457fcabc41d0
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 N1d97a685edef4bc4808a39646ab9e49c schema:name doi
44 schema:value 10.1007/978-3-540-39611-6_23
45 rdf:type schema:PropertyValue
46 N30d2666f92f040eda422f387689d2bfa schema:name dimensions_id
47 schema:value pub.1049147060
48 rdf:type schema:PropertyValue
49 N3341eea4c641488b8817c97184b6ade1 schema:affiliation https://www.grid.ac/institutes/grid.417969.4
50 schema:familyName Bhadra
51 schema:givenName Sandeep
52 rdf:type schema:Person
53 N3551bb094c2042f6b09d8560e389feef rdf:first sg:person.014027376043.50
54 rdf:rest rdf:nil
55 N42c2d5917e794ced98cc0508d4b3fff8 schema:familyName Barbeau
56 schema:givenName Michel
57 rdf:type schema:Person
58 N4cc98741fe8948f59909b5bad94a58de rdf:first N3341eea4c641488b8817c97184b6ade1
59 rdf:rest N3551bb094c2042f6b09d8560e389feef
60 N6b20a00677c74c73981203f98f952566 schema:isbn 978-3-540-20260-8
61 978-3-540-39611-6
62 schema:name Ad-Hoc, Mobile, and Wireless Networks
63 rdf:type schema:Book
64 N9ee93a98a0ee4ef6be865ce3c49f3c25 schema:familyName Kranakis
65 schema:givenName Evangelos
66 rdf:type schema:Person
67 Nad41cfc9abff4ba7aeeff1ae4eadba37 schema:name readcube_id
68 schema:value ea20e0837a06014011f89189afaa8c717899b6bfb79427960fedd3699099dcf7
69 rdf:type schema:PropertyValue
70 Nb4234109372c49578eab9469d5bab7c0 schema:location Berlin, Heidelberg
71 schema:name Springer Berlin Heidelberg
72 rdf:type schema:Organisation
73 Nb6c710e598844c4ab713e9a13aedd86f schema:familyName Pierre
74 schema:givenName Samuel
75 rdf:type schema:Person
76 Nbf7baeaae45343479b91457fcabc41d0 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 Nd4eca95c865841a5aaa53676cf1f88a5 rdf:first N42c2d5917e794ced98cc0508d4b3fff8
79 rdf:rest Ne267eb612d5048daa10d365fcdbd4088
80 Ne267eb612d5048daa10d365fcdbd4088 rdf:first N9ee93a98a0ee4ef6be865ce3c49f3c25
81 rdf:rest rdf:nil
82 Nece95357829442a4a74b09372ef99541 rdf:first Nb6c710e598844c4ab713e9a13aedd86f
83 rdf:rest Nd4eca95c865841a5aaa53676cf1f88a5
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)


...