Tree edge decomposition with an application to minimum ultrametric tree approximation View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-08-14

AUTHORS

Chia-Mao Huang, Bang Ye Wu, Chang-Biau Yang

ABSTRACT

A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree. More... »

PAGES

217-230

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10878-006-9626-z

DOI

http://dx.doi.org/10.1007/s10878-006-9626-z

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, National Sun Yat-sen University, 804, Kaohsiung, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412036.2", 
          "name": [
            "Department of Computer Science and Engineering, National Sun Yat-sen University, 804, Kaohsiung, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Huang", 
        "givenName": "Chia-Mao", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, Shu-Te University, YenChau, 824, Kaohsiung, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.445041.0", 
          "name": [
            "Department of Computer Science and Information Engineering, Shu-Te University, YenChau, 824, Kaohsiung, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, National Sun Yat-sen University, 804, Kaohsiung, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412036.2", 
          "name": [
            "Department of Computer Science and Engineering, National Sun Yat-sen University, 804, Kaohsiung, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Chang-Biau", 
        "id": "sg:person.013201414347.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013201414347.02"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01188585", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004227195", 
          "https://doi.org/10.1007/bf01188585"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009885610075", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044701682", 
          "https://doi.org/10.1023/a:1009885610075"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006-08-14", 
    "datePublishedReg": "2006-08-14", 
    "description": "A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most \u23081.44 log n\u2309 (and \u2308log n\u2309 respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10878-006-9626-z", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "12"
      }
    ], 
    "keywords": [
      "minimum ultrametric tree", 
      "edge trees", 
      "ultrametric tree", 
      "trees", 
      "improved approximation algorithms", 
      "approximation algorithm", 
      "edge decomposition", 
      "tree approximation", 
      "decomposition", 
      "levels", 
      "bounds", 
      "approximation", 
      "process", 
      "subtrees", 
      "edge", 
      "problem", 
      "results", 
      "algorithm", 
      "applications", 
      "log", 
      "paper", 
      "extreme tree", 
      "edge-disjoint subtrees", 
      "Tree edge decomposition", 
      "minimum ultrametric tree approximation", 
      "ultrametric tree approximation"
    ], 
    "name": "Tree edge decomposition with an application to minimum ultrametric tree approximation", 
    "pagination": "217-230", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029685994"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10878-006-9626-z"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10878-006-9626-z", 
      "https://app.dimensions.ai/details/publication/pub.1029685994"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_430.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10878-006-9626-z"
  }
]
 

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/s10878-006-9626-z'

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/s10878-006-9626-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-006-9626-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-006-9626-z'


 

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

116 TRIPLES      22 PREDICATES      55 URIs      43 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10878-006-9626-z schema:about anzsrc-for:01
2 anzsrc-for:0101
3 anzsrc-for:0102
4 anzsrc-for:0103
5 schema:author Neb087b47be1f4e1eba05e6c3b5257ca7
6 schema:citation sg:pub.10.1007/bf01188585
7 sg:pub.10.1023/a:1009885610075
8 schema:datePublished 2006-08-14
9 schema:datePublishedReg 2006-08-14
10 schema:description A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.
11 schema:genre article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N1f4c956d5b8447f28f87cf9a6086f9d7
15 Nddc46a047a144042a224430e385a1b3a
16 sg:journal.1036683
17 schema:keywords Tree edge decomposition
18 algorithm
19 applications
20 approximation
21 approximation algorithm
22 bounds
23 decomposition
24 edge
25 edge decomposition
26 edge trees
27 edge-disjoint subtrees
28 extreme tree
29 improved approximation algorithms
30 levels
31 log
32 minimum ultrametric tree
33 minimum ultrametric tree approximation
34 paper
35 problem
36 process
37 results
38 subtrees
39 tree approximation
40 trees
41 ultrametric tree
42 ultrametric tree approximation
43 schema:name Tree edge decomposition with an application to minimum ultrametric tree approximation
44 schema:pagination 217-230
45 schema:productId N13a8ef0cd3cd4e5eaed58cae54458a1c
46 Nad568f083d74493f88412c2f54f1167d
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029685994
48 https://doi.org/10.1007/s10878-006-9626-z
49 schema:sdDatePublished 2022-01-01T18:16
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N2a1d6395945045a695a5e3b668aed81c
52 schema:url https://doi.org/10.1007/s10878-006-9626-z
53 sgo:license sg:explorer/license/
54 sgo:sdDataset articles
55 rdf:type schema:ScholarlyArticle
56 N13a8ef0cd3cd4e5eaed58cae54458a1c schema:name doi
57 schema:value 10.1007/s10878-006-9626-z
58 rdf:type schema:PropertyValue
59 N1f4c956d5b8447f28f87cf9a6086f9d7 schema:issueNumber 3
60 rdf:type schema:PublicationIssue
61 N2a1d6395945045a695a5e3b668aed81c schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N2d942cb7edab452b97c9258a11bd6e70 rdf:first sg:person.013201414347.02
64 rdf:rest rdf:nil
65 N974c1782908a4aa38a39cd764069c445 rdf:first sg:person.013045767237.23
66 rdf:rest N2d942cb7edab452b97c9258a11bd6e70
67 Nad568f083d74493f88412c2f54f1167d schema:name dimensions_id
68 schema:value pub.1029685994
69 rdf:type schema:PropertyValue
70 Nddc46a047a144042a224430e385a1b3a schema:volumeNumber 12
71 rdf:type schema:PublicationVolume
72 Nde358023e562412597ed33cd70681a12 schema:affiliation grid-institutes:grid.412036.2
73 schema:familyName Huang
74 schema:givenName Chia-Mao
75 rdf:type schema:Person
76 Neb087b47be1f4e1eba05e6c3b5257ca7 rdf:first Nde358023e562412597ed33cd70681a12
77 rdf:rest N974c1782908a4aa38a39cd764069c445
78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
79 schema:name Mathematical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
82 schema:name Pure Mathematics
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
85 schema:name Applied Mathematics
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
88 schema:name Numerical and Computational Mathematics
89 rdf:type schema:DefinedTerm
90 sg:journal.1036683 schema:issn 1382-6905
91 1573-2886
92 schema:name Journal of Combinatorial Optimization
93 schema:publisher Springer Nature
94 rdf:type schema:Periodical
95 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.445041.0
96 schema:familyName Wu
97 schema:givenName Bang Ye
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
99 rdf:type schema:Person
100 sg:person.013201414347.02 schema:affiliation grid-institutes:grid.412036.2
101 schema:familyName Yang
102 schema:givenName Chang-Biau
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013201414347.02
104 rdf:type schema:Person
105 sg:pub.10.1007/bf01188585 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004227195
106 https://doi.org/10.1007/bf01188585
107 rdf:type schema:CreativeWork
108 sg:pub.10.1023/a:1009885610075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044701682
109 https://doi.org/10.1023/a:1009885610075
110 rdf:type schema:CreativeWork
111 grid-institutes:grid.412036.2 schema:alternateName Department of Computer Science and Engineering, National Sun Yat-sen University, 804, Kaohsiung, Taiwan, R.O.C.
112 schema:name Department of Computer Science and Engineering, National Sun Yat-sen University, 804, Kaohsiung, Taiwan, R.O.C.
113 rdf:type schema:Organization
114 grid-institutes:grid.445041.0 schema:alternateName Department of Computer Science and Information Engineering, Shu-Te University, YenChau, 824, Kaohsiung, Taiwan, R.O.C.
115 schema:name Department of Computer Science and Information Engineering, Shu-Te University, YenChau, 824, Kaohsiung, Taiwan, R.O.C.
116 rdf:type schema:Organization
 




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


...