Optimal Leaf Ordering of Complete Binary Trees

Lade...
Vorschaubild
Dateien
Brandes_opus-117791.pdf
Brandes_opus-117791.pdfGröße: 149.43 KBDownloads: 292
Datum
2007
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published
Erschienen in
Journal of Discrete Algorithms. 2007, 5(3), pp. 546-552. Available under: doi: 10.1016/j.jda.2006.09.003
Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
optimal leaf ordering, bit-manipulation algorithms, permutations
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BRANDES, Ulrik, 2007. Optimal Leaf Ordering of Complete Binary Trees. In: Journal of Discrete Algorithms. 2007, 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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen