Linear-Time Algorithms for Tree Root Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Maw-Shang Chang , Ming-Tat Ko , Hsueh-I Lu

ABSTRACT

Let T be a tree on a set V of nodes. The p-th powerTp of T is the graph on V such that any two nodes u and w of V are adjacent in Tp if and only if the distance of u and w in T is at most p. Given an n-node m-edge graph G and a positive integer p, the p-th tree root problem asks for a tree T, if any, such that G=Tp. Given a graph G, the tree root problem asks for a positive integer p and a tree T, if any, such that G=Tp. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in O(n3) (respectively, O(n4)) time. In this paper, we give O(n+m)-time algorithms for both problems. More... »

PAGES

411-422

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11785293_38

DOI

http://dx.doi.org/10.1007/11785293_38

DIMENSIONS

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


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": "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Shiun, Chiayi, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Shiun, Chiayi, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Maw-Shang", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ko", 
        "givenName": "Ming-Tat", 
        "id": "sg:person.07473764745.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University, 106, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, 106, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Let T be a tree on a set V of nodes. The p-th powerTp of T is the graph on V such that any two nodes u and w of V are adjacent in Tp if and only if the distance of u and w in T is at most p. Given an n-node m-edge graph G and a positive integer p, the p-th tree root problem asks for a tree T, if any, such that G=Tp. Given a graph G, the tree root problem asks for a positive integer p and a tree T, if any, such that G=Tp. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in O(n3) (respectively, O(n4)) time. In this paper, we give O(n+m)-time algorithms for both problems.", 
    "editor": [
      {
        "familyName": "Arge", 
        "givenName": "Lars", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "Rusins", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11785293_38", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35753-7", 
        "978-3-540-35755-1"
      ], 
      "name": "Algorithm Theory \u2013 SWAT 2006", 
      "type": "Book"
    }, 
    "keywords": [
      "time algorithm", 
      "algorithm", 
      "node u", 
      "root problem", 
      "former problem", 
      "nodes", 
      "graph G", 
      "graph", 
      "tree T", 
      "Corneil", 
      "edge graph G", 
      "trees", 
      "positive integer p", 
      "integers p", 
      "distance", 
      "time", 
      "TP", 
      "Kearney", 
      "problem", 
      "paper", 
      "th powerTp", 
      "powerTp", 
      "tree root problem"
    ], 
    "name": "Linear-Time Algorithms for Tree Root Problems", 
    "pagination": "411-422", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004869830"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11785293_38"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11785293_38", 
      "https://app.dimensions.ai/details/publication/pub.1004869830"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:58", 
    "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_374.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11785293_38"
  }
]
 

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/11785293_38'

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/11785293_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11785293_38'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11785293_38'


 

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

108 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11785293_38 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1f050cdbf5074f478c81711fa95b13ee
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Let T be a tree on a set V of nodes. The p-th powerTp of T is the graph on V such that any two nodes u and w of V are adjacent in Tp if and only if the distance of u and w in T is at most p. Given an n-node m-edge graph G and a positive integer p, the p-th tree root problem asks for a tree T, if any, such that G=Tp. Given a graph G, the tree root problem asks for a positive integer p and a tree T, if any, such that G=Tp. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in O(n3) (respectively, O(n4)) time. In this paper, we give O(n+m)-time algorithms for both problems.
7 schema:editor N4f6bdba634204de7a0d734ebd9e591f7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfb8bb9ff8ffa4c96a5e477d4611aa361
12 schema:keywords Corneil
13 Kearney
14 TP
15 algorithm
16 distance
17 edge graph G
18 former problem
19 graph
20 graph G
21 integers p
22 node u
23 nodes
24 paper
25 positive integer p
26 powerTp
27 problem
28 root problem
29 th powerTp
30 time
31 time algorithm
32 tree T
33 tree root problem
34 trees
35 schema:name Linear-Time Algorithms for Tree Root Problems
36 schema:pagination 411-422
37 schema:productId N217aad9e91ae4a268fa5658d91afb8ca
38 N84ee76f7b45c4a888aa2c6247c7bdf42
39 schema:publisher Nb02d87b1db8345d6946b7bb0c82f9bfc
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004869830
41 https://doi.org/10.1007/11785293_38
42 schema:sdDatePublished 2021-11-01T18:58
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N7e58a9c85fe044e398880a35f3685af2
45 schema:url https://doi.org/10.1007/11785293_38
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N12c5666f0f5b4403a9122a586533ba13 rdf:first sg:person.013345515575.46
50 rdf:rest rdf:nil
51 N1f050cdbf5074f478c81711fa95b13ee rdf:first sg:person.013174232477.45
52 rdf:rest N53f194e4a6504077b5235d924d2a7a6b
53 N217aad9e91ae4a268fa5658d91afb8ca schema:name dimensions_id
54 schema:value pub.1004869830
55 rdf:type schema:PropertyValue
56 N4f6bdba634204de7a0d734ebd9e591f7 rdf:first N92760ba6815b4a2295b7f9a591abad63
57 rdf:rest N74495c4dee8f4d1e866f90697b3d6328
58 N53f194e4a6504077b5235d924d2a7a6b rdf:first sg:person.07473764745.12
59 rdf:rest N12c5666f0f5b4403a9122a586533ba13
60 N74495c4dee8f4d1e866f90697b3d6328 rdf:first Nb0e41488e7164551a2d5b5978c2652e6
61 rdf:rest rdf:nil
62 N7e58a9c85fe044e398880a35f3685af2 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N84ee76f7b45c4a888aa2c6247c7bdf42 schema:name doi
65 schema:value 10.1007/11785293_38
66 rdf:type schema:PropertyValue
67 N92760ba6815b4a2295b7f9a591abad63 schema:familyName Arge
68 schema:givenName Lars
69 rdf:type schema:Person
70 Nb02d87b1db8345d6946b7bb0c82f9bfc schema:name Springer Nature
71 rdf:type schema:Organisation
72 Nb0e41488e7164551a2d5b5978c2652e6 schema:familyName Freivalds
73 schema:givenName Rusins
74 rdf:type schema:Person
75 Nfb8bb9ff8ffa4c96a5e477d4611aa361 schema:isbn 978-3-540-35753-7
76 978-3-540-35755-1
77 schema:name Algorithm Theory – SWAT 2006
78 rdf:type schema:Book
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
83 schema:name Computation Theory and Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
86 schema:familyName Chang
87 schema:givenName Maw-Shang
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
89 rdf:type schema:Person
90 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
91 schema:familyName Lu
92 schema:givenName Hsueh-I
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
94 rdf:type schema:Person
95 sg:person.07473764745.12 schema:affiliation grid-institutes:grid.28665.3f
96 schema:familyName Ko
97 schema:givenName Ming-Tat
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12
99 rdf:type schema:Person
100 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University, 106, Taipei, Taiwan
101 schema:name Department of Computer Science and Information Engineering, National Taiwan University, 106, Taipei, Taiwan
102 rdf:type schema:Organization
103 grid-institutes:grid.28665.3f schema:alternateName Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan
104 schema:name Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan
105 rdf:type schema:Organization
106 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Shiun, Chiayi, Taiwan
107 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Shiun, Chiayi, Taiwan
108 rdf:type schema:Organization
 




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


...