Linear-Time Algorithms for Tree Root Problems View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2013-08-07

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 an n-node m-edge 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

471-495

References to SciGraph publications

  • 2006. Linear-Time Algorithms for Tree Root Problems in ALGORITHM THEORY – SWAT 2006
  • 1961-04. On rigid circuit graphs in ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSITÄT HAMBURG
  • 2008-01-30. Independent Sets in Graph Powers are Almost Contained in Juntas in GEOMETRIC AND FUNCTIONAL ANALYSIS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-013-9815-y

    DOI

    http://dx.doi.org/10.1007/s00453-013-9815-y

    DIMENSIONS

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


    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, Hungkuang University, 43302, Taichung City, Shalu District, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.411432.1", 
              "name": [
                "Department of Computer Science and Information Engineering, Hungkuang University, 43302, Taichung City, Shalu District, 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, 1 Roosevelt Road, Section 4, 106, Taipei, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.19188.39", 
              "name": [
                "Department of Computer Science and Information Engineering, National Taiwan University, 1 Roosevelt Road, Section 4, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00039-008-0651-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035437203", 
              "https://doi.org/10.1007/s00039-008-0651-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02992776", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031195160", 
              "https://doi.org/10.1007/bf02992776"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11785293_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004869830", 
              "https://doi.org/10.1007/11785293_38"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-08-07", 
        "datePublishedReg": "2013-08-07", 
        "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\u00a0p. Given an n-node m-edge graph G and a positive integer\u00a0p, the p-th tree root problem asks for a tree T, if any, such that G=Tp. Given an n-node m-edge graph\u00a0G, the tree root problem asks for a positive integer p and a tree\u00a0T, 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.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-013-9815-y", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "71"
          }
        ], 
        "keywords": [
          "time algorithm", 
          "edge graph", 
          "algorithm", 
          "node u", 
          "root problem", 
          "former problem", 
          "nodes", 
          "graph", 
          "Corneil", 
          "edge graph G", 
          "graph G", 
          "trees", 
          "tree T", 
          "integers", 
          "distance", 
          "positive integer p", 
          "time", 
          "integers p", 
          "positive integer", 
          "TP", 
          "Kearney", 
          "problem", 
          "paper", 
          "th powerTp", 
          "powerTp", 
          "tree root problem"
        ], 
        "name": "Linear-Time Algorithms for Tree Root Problems", 
        "pagination": "471-495", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1034531402"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-013-9815-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-013-9815-y", 
          "https://app.dimensions.ai/details/publication/pub.1034531402"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:19", 
        "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/article/article_598.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-013-9815-y"
      }
    ]
     

    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/s00453-013-9815-y'

    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/s00453-013-9815-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-013-9815-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-013-9815-y'


     

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

    116 TRIPLES      22 PREDICATES      54 URIs      43 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-013-9815-y schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N0bf3a63c32dc47e6b9d686f4341450a7
    4 schema:citation sg:pub.10.1007/11785293_38
    5 sg:pub.10.1007/bf02992776
    6 sg:pub.10.1007/s00039-008-0651-1
    7 schema:datePublished 2013-08-07
    8 schema:datePublishedReg 2013-08-07
    9 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 an n-node m-edge 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.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N1ea65a4dcf434c21bbb784eec809d93b
    14 Ned9857bab23a4faab179cbd7b0421c05
    15 sg:journal.1047644
    16 schema:keywords Corneil
    17 Kearney
    18 TP
    19 algorithm
    20 distance
    21 edge graph
    22 edge graph G
    23 former problem
    24 graph
    25 graph G
    26 integers
    27 integers p
    28 node u
    29 nodes
    30 paper
    31 positive integer
    32 positive integer p
    33 powerTp
    34 problem
    35 root problem
    36 th powerTp
    37 time
    38 time algorithm
    39 tree T
    40 tree root problem
    41 trees
    42 schema:name Linear-Time Algorithms for Tree Root Problems
    43 schema:pagination 471-495
    44 schema:productId Na02b75afcf7048d3a5c00bd58f83b437
    45 Ndf2dd5d4bf9b462780035834c75e7395
    46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034531402
    47 https://doi.org/10.1007/s00453-013-9815-y
    48 schema:sdDatePublished 2021-11-01T18:19
    49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    50 schema:sdPublisher N0e6057755d7e4920968711a5ca2ab04e
    51 schema:url https://doi.org/10.1007/s00453-013-9815-y
    52 sgo:license sg:explorer/license/
    53 sgo:sdDataset articles
    54 rdf:type schema:ScholarlyArticle
    55 N0bf3a63c32dc47e6b9d686f4341450a7 rdf:first sg:person.013174232477.45
    56 rdf:rest Nd5708862ed564fe88c8c5c2b5459b486
    57 N0e6057755d7e4920968711a5ca2ab04e schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 N1ea65a4dcf434c21bbb784eec809d93b schema:volumeNumber 71
    60 rdf:type schema:PublicationVolume
    61 Na02b75afcf7048d3a5c00bd58f83b437 schema:name doi
    62 schema:value 10.1007/s00453-013-9815-y
    63 rdf:type schema:PropertyValue
    64 Nd5708862ed564fe88c8c5c2b5459b486 rdf:first sg:person.07473764745.12
    65 rdf:rest Nf4fad22c6c9a407bbd803bfa6622579b
    66 Ndf2dd5d4bf9b462780035834c75e7395 schema:name dimensions_id
    67 schema:value pub.1034531402
    68 rdf:type schema:PropertyValue
    69 Ned9857bab23a4faab179cbd7b0421c05 schema:issueNumber 2
    70 rdf:type schema:PublicationIssue
    71 Nf4fad22c6c9a407bbd803bfa6622579b rdf:first sg:person.013345515575.46
    72 rdf:rest rdf:nil
    73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Information and Computing Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Computation Theory and Mathematics
    78 rdf:type schema:DefinedTerm
    79 sg:journal.1047644 schema:issn 0178-4617
    80 1432-0541
    81 schema:name Algorithmica
    82 schema:publisher Springer Nature
    83 rdf:type schema:Periodical
    84 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.411432.1
    85 schema:familyName Chang
    86 schema:givenName Maw-Shang
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
    88 rdf:type schema:Person
    89 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
    90 schema:familyName Lu
    91 schema:givenName Hsueh-I
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
    93 rdf:type schema:Person
    94 sg:person.07473764745.12 schema:affiliation grid-institutes:grid.28665.3f
    95 schema:familyName Ko
    96 schema:givenName Ming-Tat
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12
    98 rdf:type schema:Person
    99 sg:pub.10.1007/11785293_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004869830
    100 https://doi.org/10.1007/11785293_38
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/bf02992776 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031195160
    103 https://doi.org/10.1007/bf02992776
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/s00039-008-0651-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035437203
    106 https://doi.org/10.1007/s00039-008-0651-1
    107 rdf:type schema:CreativeWork
    108 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University, 1 Roosevelt Road, Section 4, 106, Taipei, Taiwan
    109 schema:name Department of Computer Science and Information Engineering, National Taiwan University, 1 Roosevelt Road, Section 4, 106, Taipei, Taiwan
    110 rdf:type schema:Organization
    111 grid-institutes:grid.28665.3f schema:alternateName Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan
    112 schema:name Institute of Information Science, Academia Sinica, 115, Taipei, Taiwan
    113 rdf:type schema:Organization
    114 grid-institutes:grid.411432.1 schema:alternateName Department of Computer Science and Information Engineering, Hungkuang University, 43302, Taichung City, Shalu District, Taiwan
    115 schema:name Department of Computer Science and Information Engineering, Hungkuang University, 43302, Taichung City, Shalu District, Taiwan
    116 rdf:type schema:Organization
     




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


    ...