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": "2021-12-01T19:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_423.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 N9e136b1fc4d440a085ce97a0884340ab
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 Nd5916ec6d6f64717a2f2081694dc2940
15 Nf5f2842a49c84bb783553e599a9b610c
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 N3109e674ac534b9eba1ec77ba23ab5c1
46 N9f2a2091c4a442719504e1f120faf16c
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029685994
48 https://doi.org/10.1007/s10878-006-9626-z
49 schema:sdDatePublished 2021-12-01T19:18
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N698fab55be234e698b9d5b6d2238dca8
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 N3109e674ac534b9eba1ec77ba23ab5c1 schema:name dimensions_id
57 schema:value pub.1029685994
58 rdf:type schema:PropertyValue
59 N4fdb1f2caf9e40f7933aa488260af7b2 rdf:first sg:person.013201414347.02
60 rdf:rest rdf:nil
61 N698fab55be234e698b9d5b6d2238dca8 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N9e136b1fc4d440a085ce97a0884340ab rdf:first Nc11321b42b04498381960d3eec265871
64 rdf:rest Nae85fb376ac545db98fb546472bf5815
65 N9f2a2091c4a442719504e1f120faf16c schema:name doi
66 schema:value 10.1007/s10878-006-9626-z
67 rdf:type schema:PropertyValue
68 Nae85fb376ac545db98fb546472bf5815 rdf:first sg:person.013045767237.23
69 rdf:rest N4fdb1f2caf9e40f7933aa488260af7b2
70 Nc11321b42b04498381960d3eec265871 schema:affiliation grid-institutes:grid.412036.2
71 schema:familyName Huang
72 schema:givenName Chia-Mao
73 rdf:type schema:Person
74 Nd5916ec6d6f64717a2f2081694dc2940 schema:volumeNumber 12
75 rdf:type schema:PublicationVolume
76 Nf5f2842a49c84bb783553e599a9b610c schema:issueNumber 3
77 rdf:type schema:PublicationIssue
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)


...