The 3-Steiner Root Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Maw-Shang Chang , Ming-Tat Ko

ABSTRACT

For a graph G and a positive integer k, the k-power of G is the graph Gk with V(G) as its vertex set and {(u,v)| u, v ∈ V(G), dG(u, v) ≤ k} as its edge set where dG(u,v) is the distance between u and v in graph G. The k-Steiner root problem on a graph G asks for a tree T with V(G) ⊆ V(T) and G is the subgraph of Tk induced by V(G). If such a tree T exists, we call it a k-Steiner root of G. This paper gives a linear time algorithm for the 3-Steiner root problem. Consider an unrooted tree T with leaves one-to-one labeled by the elements of a set V. The k-leaf power of T is a graph, denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$T_{L}^{k}$\end{document}, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$T_{L}^{k} = (V, E)$\end{document}, where E = {(u,v) |u, v ∈ V and dT(u,v) ≤ k}. We call T a k-leaf root of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$T_{L}^{k}$\end{document}. The k-leaf power recognition problem is to decide whether a graph has such a k-leaf root. The complexity of this problem is still open for k ≥ 5 [6]. It can be solved in polynomial time if the (k − 2)-Steiner root problem can be solved in polynomial time [6]. Our result implies that the k-leaf power recognition problem can be solved in linear time for k = 5. More... »

PAGES

109-120

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74839-7_11

DOI

http://dx.doi.org/10.1007/978-3-540-74839-7_11

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, R.O.C."
          ], 
          "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, Taipei 115, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.506928.0", 
          "name": [
            "Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C."
          ], 
          "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"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "For a graph G and a positive integer k, the k-power of G is the graph Gk with V(G) as its vertex set and {(u,v)| u, v\u2009\u2208\u2009V(G),\u00a0 dG(u, v) \u2264\u2009k} as its edge set where dG(u,v) is the distance between u and v in graph G. The k-Steiner root problem on a graph G asks for a tree T with V(G)\u2009\u2286\u2009V(T) and G is the subgraph of Tk induced by V(G). If such a tree T exists, we call it a k-Steiner root of G. This paper gives a linear time algorithm for the 3-Steiner root problem. Consider an unrooted tree T with leaves one-to-one labeled by the elements of a set V. The k-leaf power of T is a graph, denoted \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$T_{L}^{k}$\\end{document}, with \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$T_{L}^{k} = (V, E)$\\end{document}, where E\u2009=\u2009{(u,v) |u, v\u2009\u2208\u2009V \u00a0 and \u00a0 dT(u,v)\u2009\u2264\u2009k}. We call T a k-leaf root of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$T_{L}^{k}$\\end{document}. The k-leaf power recognition problem is to decide whether a graph has such a k-leaf root. The complexity of this problem is still open for k\u2009\u2265\u20095 [6]. It can be solved in polynomial time if the (k\u2009\u2212\u20092)-Steiner root problem can be solved in polynomial time [6]. Our result implies that the k-leaf power recognition problem can be solved in linear time for k\u2009=\u20095.", 
    "editor": [
      {
        "familyName": "Brandst\u00e4dt", 
        "givenName": "Andreas", 
        "type": "Person"
      }, 
      {
        "familyName": "Kratsch", 
        "givenName": "Dieter", 
        "type": "Person"
      }, 
      {
        "familyName": "M\u00fcller", 
        "givenName": "Haiko", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74839-7_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74838-0", 
        "978-3-540-74839-7"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "leaf root", 
      "roots", 
      "leaf powers", 
      "Steiner roots", 
      "unrooted tree T", 
      "tree T", 
      "TK", 
      "GK", 
      "G.", 
      "elements", 
      "distance", 
      "time", 
      "complexity", 
      "results", 
      "edge", 
      "one", 
      "root problem", 
      "linear time algorithm", 
      "power", 
      "problem", 
      "subgraphs", 
      "vertices", 
      "graph G.", 
      "paper", 
      "time algorithm", 
      "algorithm", 
      "graph", 
      "linear time", 
      "recognition problem", 
      "polynomial time", 
      "graph G", 
      "positive integer k", 
      "integer k", 
      "graph Gk", 
      "Steiner root problem", 
      "subgraph of Tk", 
      "leaf power recognition problem", 
      "power recognition problem"
    ], 
    "name": "The 3-Steiner Root Problem", 
    "pagination": "109-120", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013595771"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74839-7_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74839-7_11", 
      "https://app.dimensions.ai/details/publication/pub.1013595771"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "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_357.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-74839-7_11"
  }
]
 

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-74839-7_11'

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-74839-7_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74839-7_11'

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-74839-7_11'


 

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

118 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74839-7_11 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N78d76018c37b41daa9256ab64926a153
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description For a graph G and a positive integer k, the k-power of G is the graph Gk with V(G) as its vertex set and {(u,v)| u, v ∈ V(G),  dG(u, v) ≤ k} as its edge set where dG(u,v) is the distance between u and v in graph G. The k-Steiner root problem on a graph G asks for a tree T with V(G) ⊆ V(T) and G is the subgraph of Tk induced by V(G). If such a tree T exists, we call it a k-Steiner root of G. This paper gives a linear time algorithm for the 3-Steiner root problem. Consider an unrooted tree T with leaves one-to-one labeled by the elements of a set V. The k-leaf power of T is a graph, denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$T_{L}^{k}$\end{document}, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$T_{L}^{k} = (V, E)$\end{document}, where E = {(u,v) |u, v ∈ V   and   dT(u,v) ≤ k}. We call T a k-leaf root of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$T_{L}^{k}$\end{document}. The k-leaf power recognition problem is to decide whether a graph has such a k-leaf root. The complexity of this problem is still open for k ≥ 5 [6]. It can be solved in polynomial time if the (k − 2)-Steiner root problem can be solved in polynomial time [6]. Our result implies that the k-leaf power recognition problem can be solved in linear time for k = 5.
7 schema:editor N6aa3e6070c1c499b9a21abdba23c0a8c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N61f92a519a694bb1a4c22ce9b6690e85
12 schema:keywords G.
13 GK
14 Steiner root problem
15 Steiner roots
16 TK
17 algorithm
18 complexity
19 distance
20 edge
21 elements
22 graph
23 graph G
24 graph G.
25 graph Gk
26 integer k
27 leaf power recognition problem
28 leaf powers
29 leaf root
30 linear time
31 linear time algorithm
32 one
33 paper
34 polynomial time
35 positive integer k
36 power
37 power recognition problem
38 problem
39 recognition problem
40 results
41 root problem
42 roots
43 subgraph of Tk
44 subgraphs
45 time
46 time algorithm
47 tree T
48 unrooted tree T
49 vertices
50 schema:name The 3-Steiner Root Problem
51 schema:pagination 109-120
52 schema:productId N7276da38a8ea43deb01be49a33d0accd
53 Nbca9b96b4ada460f86ee708face22416
54 schema:publisher N54ad3f37035746b484dd54ba3c230e42
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013595771
56 https://doi.org/10.1007/978-3-540-74839-7_11
57 schema:sdDatePublished 2021-11-01T18:57
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher Nd36e6aa93de54f4dbcdf562595e9305c
60 schema:url https://doi.org/10.1007/978-3-540-74839-7_11
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N30f98ad854ca480a8398f4af18e60e7b schema:familyName Müller
65 schema:givenName Haiko
66 rdf:type schema:Person
67 N44b9812305c743098a77e29115e441c7 schema:familyName Kratsch
68 schema:givenName Dieter
69 rdf:type schema:Person
70 N54ad3f37035746b484dd54ba3c230e42 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N60bd6fd29b704270b28ad17dc9c07be8 rdf:first N30f98ad854ca480a8398f4af18e60e7b
73 rdf:rest rdf:nil
74 N61f92a519a694bb1a4c22ce9b6690e85 schema:isbn 978-3-540-74838-0
75 978-3-540-74839-7
76 schema:name Graph-Theoretic Concepts in Computer Science
77 rdf:type schema:Book
78 N6aa3e6070c1c499b9a21abdba23c0a8c rdf:first Nde29cf34485a46b9a0ac860acbb8ef90
79 rdf:rest Nc69fc71ab89c47c58945fc6e6d20c99b
80 N7276da38a8ea43deb01be49a33d0accd schema:name dimensions_id
81 schema:value pub.1013595771
82 rdf:type schema:PropertyValue
83 N78d76018c37b41daa9256ab64926a153 rdf:first sg:person.013174232477.45
84 rdf:rest Naa2ebb1baf5e4400a231fc7b5ecff6d8
85 Naa2ebb1baf5e4400a231fc7b5ecff6d8 rdf:first sg:person.07473764745.12
86 rdf:rest rdf:nil
87 Nbca9b96b4ada460f86ee708face22416 schema:name doi
88 schema:value 10.1007/978-3-540-74839-7_11
89 rdf:type schema:PropertyValue
90 Nc69fc71ab89c47c58945fc6e6d20c99b rdf:first N44b9812305c743098a77e29115e441c7
91 rdf:rest N60bd6fd29b704270b28ad17dc9c07be8
92 Nd36e6aa93de54f4dbcdf562595e9305c schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 Nde29cf34485a46b9a0ac860acbb8ef90 schema:familyName Brandstädt
95 schema:givenName Andreas
96 rdf:type schema:Person
97 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
98 schema:name Biological Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
101 schema:name Plant Biology
102 rdf:type schema:DefinedTerm
103 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
104 schema:familyName Chang
105 schema:givenName Maw-Shang
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
107 rdf:type schema:Person
108 sg:person.07473764745.12 schema:affiliation grid-institutes:grid.506928.0
109 schema:familyName Ko
110 schema:givenName Ming-Tat
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07473764745.12
112 rdf:type schema:Person
113 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, R.O.C.
114 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, R.O.C.
115 rdf:type schema:Organization
116 grid-institutes:grid.506928.0 schema:alternateName Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C.
117 schema:name Institute of Information Science, Academia Sinica, Taipei 115, Taiwan, R.O.C.
118 rdf:type schema:Organization
 




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


...