Optimal Leaf Ordering of Complete Binary Trees

Loading...
Thumbnail Image
Date
2007
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
DOI (citable link)
ArXiv-ID
International patent number
EU project number
Project
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Journal article
Publication status
Published in
Journal of Discrete Algorithms ; 5 (2007), 3. - pp. 546-552
Abstract
Ordering a set of items so as to minimize the sum of distances between consecutive elements is a fundamental optimization problem occurring in many settings. While it is View the MathML source-hard in general, it becomes polynomially solvable if the set of feasible permutations is restricted to be compatible with a tree of bounded degree. We present a new algorithm for the elementary case of ordering the n leaves of a binary tree with height View the MathML source. Our algorithm requires View the MathML source time and View the MathML source space. While the running time is a log-factor away from being asymptotically optimal, the algorithm is conceptually simple, easy to implement, and highly practical. Its implementation requires little more than a few bit-manipulations.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
optimal leaf ordering,bit-manipulation algorithms,permutations
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690BRANDES, Ulrik, 2007. Optimal Leaf Ordering of Complete Binary Trees. In: Journal of Discrete Algorithms. 5(3), pp. 546-552. Available under: doi: 10.1016/j.jda.2006.09.003
BibTex
@article{Brandes2007Optim-3022,
  year={2007},
  doi={10.1016/j.jda.2006.09.003},
  title={Optimal Leaf Ordering of Complete Binary Trees},
  number={3},
  volume={5},
  journal={Journal of Discrete Algorithms},
  pages={546--552},
  author={Brandes, Ulrik}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/3022">
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:bibliographicCitation>Publ. in: Journal of Discrete Algorithms 5 (2007), 3, pp. 546-552</dcterms:bibliographicCitation>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/3022/1/Brandes_opus-117791.pdf"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/3022/1/Brandes_opus-117791.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/3022"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>Optimal Leaf Ordering of Complete Binary Trees</dcterms:title>
    <dc:language>eng</dc:language>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:48Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dcterms:issued>2007</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:48Z</dc:date>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dcterms:abstract xml:lang="eng">Ordering a set of items so as to minimize the sum of distances between consecutive elements is a fundamental optimization problem occurring in many settings. While it is View the MathML source-hard in general, it becomes polynomially solvable if the set of feasible permutations is restricted to be compatible with a tree of bounded degree. We present a new algorithm for the elementary case of ordering the n leaves of a binary tree with height View the MathML source. Our algorithm requires View the MathML source  time and View the MathML source  space. While the running time is a log-factor away from being asymptotically optimal, the algorithm is conceptually simple, easy to implement, and highly practical. Its implementation requires little more than a few bit-manipulations.</dcterms:abstract>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
Test date of URL
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes
Refereed