Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Zhi-Zhong Chen , Tatsuie Tsukiji

ABSTRACT

The Phylogenetic kth Root Problem (PRk) is theproblem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) (u, v) ∈ E if and only if the distance between u and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists, is called a phylogenetickth root of graph G. The computational complexity of PRk is open, except for k ≤ 4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connectedG has such a phylogenetic kth root, and if so, demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs. More... »

PAGES

308-319

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30559-0_26

DOI

http://dx.doi.org/10.1007/978-3-540-30559-0_26

DIMENSIONS

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


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": "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Info. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Info. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tsukiji", 
        "givenName": "Tatsuie", 
        "id": "sg:person.012341333755.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012341333755.13"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "The Phylogenetic kth Root Problem (PRk) is theproblem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1)\u00a0T has no degree-2 internal nodes, (2)\u00a0the external nodes (i.e. leaves) of T are exactly the elements of V, and (3)\u00a0(u, v) \u2208 E if and only if the distance between u and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists, is called a phylogenetickth root of graph G. The computational complexity of PRk is open, except for k \u2264 4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connectedG has such a phylogenetic kth root, and if so, demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs.", 
    "editor": [
      {
        "familyName": "Hromkovi\u010d", 
        "givenName": "Juraj", 
        "type": "Person"
      }, 
      {
        "familyName": "Nagl", 
        "givenName": "Manfred", 
        "type": "Person"
      }, 
      {
        "familyName": "Westfechtel", 
        "givenName": "Bernhard", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30559-0_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24132-4", 
        "978-3-540-30559-0"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "linear time algorithm", 
      "disconnected graphs", 
      "tree T", 
      "computational complexity", 
      "kth roots", 
      "graph G.", 
      "natural restrictions", 
      "Chen et al", 
      "maximum degree", 
      "graph", 
      "threshold k.", 
      "algorithm", 
      "internal nodes", 
      "root problem", 
      "et al", 
      "external nodes", 
      "problem", 
      "nodes", 
      "complexity", 
      "G.", 
      "phylogenetic roots", 
      "constants", 
      "distance", 
      "restriction", 
      "al", 
      "work", 
      "roots", 
      "exists", 
      "elements", 
      "degree", 
      "PRK", 
      "paper"
    ], 
    "name": "Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs", 
    "pagination": "308-319", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046352613"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30559-0_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30559-0_26", 
      "https://app.dimensions.ai/details/publication/pub.1046352613"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_389.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30559-0_26"
  }
]
 

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-30559-0_26'

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-30559-0_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30559-0_26'

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-30559-0_26'


 

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

111 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30559-0_26 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1340b80592e547398749befdc564b2a8
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description The Phylogenetic kth Root Problem (PRk) is theproblem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) (u, v) ∈ E if and only if the distance between u and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists, is called a phylogenetickth root of graph G. The computational complexity of PRk is open, except for k ≤ 4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connectedG has such a phylogenetic kth root, and if so, demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs.
7 schema:editor Nc638daba52c744c48e6ad13840d53f76
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5673354c928d43c087c7845cd305d7cd
12 schema:keywords Chen et al
13 G.
14 PRK
15 al
16 algorithm
17 complexity
18 computational complexity
19 constants
20 degree
21 disconnected graphs
22 distance
23 elements
24 et al
25 exists
26 external nodes
27 graph
28 graph G.
29 internal nodes
30 kth roots
31 linear time algorithm
32 maximum degree
33 natural restrictions
34 nodes
35 paper
36 phylogenetic roots
37 problem
38 restriction
39 root problem
40 roots
41 threshold k.
42 tree T
43 work
44 schema:name Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
45 schema:pagination 308-319
46 schema:productId Nba975f23b89f47069dce3c073b26aab1
47 Nec29024245a841a6b3af09e1c676e6b8
48 schema:publisher Nc34ecccbcfc4441f9217d44884caf1a3
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046352613
50 https://doi.org/10.1007/978-3-540-30559-0_26
51 schema:sdDatePublished 2022-05-20T07:47
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N04d7bf6445284a6a85bca57688534a3c
54 schema:url https://doi.org/10.1007/978-3-540-30559-0_26
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N04d7bf6445284a6a85bca57688534a3c schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N1340b80592e547398749befdc564b2a8 rdf:first sg:person.015654265661.98
61 rdf:rest Nbf886f2b85ee4cc88113c75aa086c618
62 N5673354c928d43c087c7845cd305d7cd schema:isbn 978-3-540-24132-4
63 978-3-540-30559-0
64 schema:name Graph-Theoretic Concepts in Computer Science
65 rdf:type schema:Book
66 N7894df41a3a246c29f0a6fe123603f7e rdf:first Nc8e4d75e402c44e999ff278da5da42a1
67 rdf:rest rdf:nil
68 N9708e73f9e6b4b6991a5d50594dec088 rdf:first Nb74d3b3b62854a8d80b697d45373935d
69 rdf:rest N7894df41a3a246c29f0a6fe123603f7e
70 Nb74d3b3b62854a8d80b697d45373935d schema:familyName Nagl
71 schema:givenName Manfred
72 rdf:type schema:Person
73 Nba975f23b89f47069dce3c073b26aab1 schema:name dimensions_id
74 schema:value pub.1046352613
75 rdf:type schema:PropertyValue
76 Nbf886f2b85ee4cc88113c75aa086c618 rdf:first sg:person.012341333755.13
77 rdf:rest rdf:nil
78 Nc34ecccbcfc4441f9217d44884caf1a3 schema:name Springer Nature
79 rdf:type schema:Organisation
80 Nc638daba52c744c48e6ad13840d53f76 rdf:first Ne6fb689038494953bffe2ffd4e6bdfaf
81 rdf:rest N9708e73f9e6b4b6991a5d50594dec088
82 Nc8e4d75e402c44e999ff278da5da42a1 schema:familyName Westfechtel
83 schema:givenName Bernhard
84 rdf:type schema:Person
85 Ne6fb689038494953bffe2ffd4e6bdfaf schema:familyName Hromkovič
86 schema:givenName Juraj
87 rdf:type schema:Person
88 Nec29024245a841a6b3af09e1c676e6b8 schema:name doi
89 schema:value 10.1007/978-3-540-30559-0_26
90 rdf:type schema:PropertyValue
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.012341333755.13 schema:affiliation grid-institutes:grid.412773.4
98 schema:familyName Tsukiji
99 schema:givenName Tatsuie
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012341333755.13
101 rdf:type schema:Person
102 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
103 schema:familyName Chen
104 schema:givenName Zhi-Zhong
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
106 rdf:type schema:Person
107 grid-institutes:grid.412773.4 schema:alternateName Dept. of Info. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
108 Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
109 schema:name Dept. of Info. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
110 Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
111 rdf:type schema:Organization
 




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


...