The 3-Steiner Root Problem

Ontology type: schema:Chapter

Chapter Info

DATE

2007-01-01

AUTHORS 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

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-74838-0
978-3-540-74839-7

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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",
"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"
}
]

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'

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
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
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
59 schema:sdPublisher Nd36e6aa93de54f4dbcdf562595e9305c
60 schema:url https://doi.org/10.1007/978-3-540-74839-7_11
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
65 schema:givenName Haiko
66 rdf:type schema:Person
67 N44b9812305c743098a77e29115e441c7 schema:familyName Kratsch
68 schema:givenName Dieter
69 rdf:type schema:Person
71 rdf:type schema:Organisation
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
88 schema:value 10.1007/978-3-540-74839-7_11
89 rdf:type schema:PropertyValue
90 Nc69fc71ab89c47c58945fc6e6d20c99b rdf:first N44b9812305c743098a77e29115e441c7
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