What costs are minimized by Huffman trees?

We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2005, Vol.19 (1), p.46-68
Main Authors: FORST, Gunnar, THORUP, Anders
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Coding, codes
Combinatorics
Combinatorics. Ordered structures
Costs
Exact sciences and technology
Graph theory
Information, signal and communications theory
Mathematics
Sciences and techniques of general use
Signal and communications theory
Telecommunications and information theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c254t-73e5295e535a33c7dc5383e344b7ccf9961d332ce61af065f39c21d2db7715313
container_end_page 68
container_issue 1
container_start_page 46
container_title SIAM journal on discrete mathematics
container_volume 19
creator FORST, Gunnar
THORUP, Anders
description We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct is an algorithm transforming an arbitrary weighted tree into a Huffman tree; for a given tree, the maximal number of steps that may be taken by this algorithm is a numerical measure of how far the tree is from being a Huffman tree.
doi_str_mv 10.1137/S0895480103421725
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_925645549</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2599592461</sourcerecordid><originalsourceid>FETCH-LOGICAL-c254t-73e5295e535a33c7dc5383e344b7ccf9961d332ce61af065f39c21d2db7715313</originalsourceid><addsrcrecordid>eNplkEFLxDAUhIMoWFd_gLcieBGqeXl5zeYksqgrLHhQ8VjSNMEu23ZN2sP6623ZBQ-e5jDzzcAwdgn8FgDV3Rufa5JzDhylACXoiCXANWUKZH7MksnOJv-UncW45hykBErYzeeX6VPbxT6mJri0qdu6qX9clZa7dDl435g27YNz8f6cnXizie7ioDP28fT4vlhmq9fnl8XDKrOCZJ8pdCQ0OUIyiFZVlnCODqUslbVe6xwqRGFdDsbznDxqK6ASVakUEALO2NW-dxu678HFvlh3Q2jHyUILyiWR1GMI9iEbuhiD88U21I0JuwJ4MT1S_HtkZK4PxSZas_HBtLaOf6Airrjm-AvV9F1g</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>925645549</pqid></control><display><type>article</type><title>What costs are minimized by Huffman trees?</title><source>SIAM Journals Archive</source><source>ABI/INFORM Global</source><creator>FORST, Gunnar ; THORUP, Anders</creator><creatorcontrib>FORST, Gunnar ; THORUP, Anders</creatorcontrib><description>We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct is an algorithm transforming an arbitrary weighted tree into a Huffman tree; for a given tree, the maximal number of steps that may be taken by this algorithm is a numerical measure of how far the tree is from being a Huffman tree.</description><identifier>ISSN: 0895-4801</identifier><identifier>EISSN: 1095-7146</identifier><identifier>DOI: 10.1137/S0895480103421725</identifier><identifier>CODEN: SJDMEC</identifier><language>eng</language><publisher>Philadelphia, PA: Society for Industrial and Applied Mathematics</publisher><subject>Algorithms ; Applied sciences ; Coding, codes ; Combinatorics ; Combinatorics. Ordered structures ; Costs ; Exact sciences and technology ; Graph theory ; Information, signal and communications theory ; Mathematics ; Sciences and techniques of general use ; Signal and communications theory ; Telecommunications and information theory</subject><ispartof>SIAM journal on discrete mathematics, 2005, Vol.19 (1), p.46-68</ispartof><rights>2006 INIST-CNRS</rights><rights>[Copyright] © 2005 Society for Industrial and Applied Mathematics</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c254t-73e5295e535a33c7dc5383e344b7ccf9961d332ce61af065f39c21d2db7715313</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/925645549?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,3171,4009,11668,27902,27903,27904,36039,44342</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=17507090$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>FORST, Gunnar</creatorcontrib><creatorcontrib>THORUP, Anders</creatorcontrib><title>What costs are minimized by Huffman trees?</title><title>SIAM journal on discrete mathematics</title><description>We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct is an algorithm transforming an arbitrary weighted tree into a Huffman tree; for a given tree, the maximal number of steps that may be taken by this algorithm is a numerical measure of how far the tree is from being a Huffman tree.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Coding, codes</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Costs</subject><subject>Exact sciences and technology</subject><subject>Graph theory</subject><subject>Information, signal and communications theory</subject><subject>Mathematics</subject><subject>Sciences and techniques of general use</subject><subject>Signal and communications theory</subject><subject>Telecommunications and information theory</subject><issn>0895-4801</issn><issn>1095-7146</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2005</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNplkEFLxDAUhIMoWFd_gLcieBGqeXl5zeYksqgrLHhQ8VjSNMEu23ZN2sP6623ZBQ-e5jDzzcAwdgn8FgDV3Rufa5JzDhylACXoiCXANWUKZH7MksnOJv-UncW45hykBErYzeeX6VPbxT6mJri0qdu6qX9clZa7dDl435g27YNz8f6cnXizie7ioDP28fT4vlhmq9fnl8XDKrOCZJ8pdCQ0OUIyiFZVlnCODqUslbVe6xwqRGFdDsbznDxqK6ASVakUEALO2NW-dxu678HFvlh3Q2jHyUILyiWR1GMI9iEbuhiD88U21I0JuwJ4MT1S_HtkZK4PxSZas_HBtLaOf6Airrjm-AvV9F1g</recordid><startdate>2005</startdate><enddate>2005</enddate><creator>FORST, Gunnar</creator><creator>THORUP, Anders</creator><general>Society for Industrial and Applied Mathematics</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7WY</scope><scope>7WZ</scope><scope>7X2</scope><scope>7XB</scope><scope>87Z</scope><scope>88A</scope><scope>88F</scope><scope>88I</scope><scope>88K</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FH</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>ATCPS</scope><scope>AZQEC</scope><scope>BBNVY</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>BHPHI</scope><scope>CCPQU</scope><scope>D1I</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KB.</scope><scope>L.-</scope><scope>L6V</scope><scope>LK8</scope><scope>M0C</scope><scope>M0K</scope><scope>M0N</scope><scope>M1Q</scope><scope>M2O</scope><scope>M2P</scope><scope>M2T</scope><scope>M7P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PATMY</scope><scope>PDBOC</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>PYCSY</scope><scope>Q9U</scope></search><sort><creationdate>2005</creationdate><title>What costs are minimized by Huffman trees?</title><author>FORST, Gunnar ; THORUP, Anders</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c254t-73e5295e535a33c7dc5383e344b7ccf9961d332ce61af065f39c21d2db7715313</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2005</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Coding, codes</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Costs</topic><topic>Exact sciences and technology</topic><topic>Graph theory</topic><topic>Information, signal and communications theory</topic><topic>Mathematics</topic><topic>Sciences and techniques of general use</topic><topic>Signal and communications theory</topic><topic>Telecommunications and information theory</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>FORST, Gunnar</creatorcontrib><creatorcontrib>THORUP, Anders</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>ABI/INFORM Complete</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>Agricultural Science Collection</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Biology Database (Alumni Edition)</collection><collection>Military Database (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Telecommunications (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>Agricultural &amp; Environmental Science Collection</collection><collection>ProQuest Central Essentials</collection><collection>Biological Science Collection</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest Natural Science Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Materials Science Collection</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer science database</collection><collection>Materials Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>ProQuest Biological Science Collection</collection><collection>ABI/INFORM Global</collection><collection>Agriculture Science Database</collection><collection>Computing Database</collection><collection>ProQuest Military Collection</collection><collection>ProQuest Research Library</collection><collection>ProQuest Science Journals</collection><collection>Telecommunications Database</collection><collection>ProQuest Biological Science Journals</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Environmental Science Database</collection><collection>Materials science collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><collection>Environmental Science Collection</collection><collection>ProQuest Central Basic</collection><jtitle>SIAM journal on discrete mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>FORST, Gunnar</au><au>THORUP, Anders</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>What costs are minimized by Huffman trees?</atitle><jtitle>SIAM journal on discrete mathematics</jtitle><date>2005</date><risdate>2005</risdate><volume>19</volume><issue>1</issue><spage>46</spage><epage>68</epage><pages>46-68</pages><issn>0895-4801</issn><eissn>1095-7146</eissn><coden>SJDMEC</coden><abstract>We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct is an algorithm transforming an arbitrary weighted tree into a Huffman tree; for a given tree, the maximal number of steps that may be taken by this algorithm is a numerical measure of how far the tree is from being a Huffman tree.</abstract><cop>Philadelphia, PA</cop><pub>Society for Industrial and Applied Mathematics</pub><doi>10.1137/S0895480103421725</doi><tpages>23</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0895-4801
ispartof SIAM journal on discrete mathematics, 2005, Vol.19 (1), p.46-68
issn 0895-4801
1095-7146
language eng
recordid cdi_proquest_journals_925645549
source SIAM Journals Archive; ABI/INFORM Global
subjects Algorithms
Applied sciences
Coding, codes
Combinatorics
Combinatorics. Ordered structures
Costs
Exact sciences and technology
Graph theory
Information, signal and communications theory
Mathematics
Sciences and techniques of general use
Signal and communications theory
Telecommunications and information theory
title What costs are minimized by Huffman trees?
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-21T13%3A55%3A57IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=What%20costs%20are%20minimized%20by%20Huffman%20trees?&rft.jtitle=SIAM%20journal%20on%20discrete%20mathematics&rft.au=FORST,%20Gunnar&rft.date=2005&rft.volume=19&rft.issue=1&rft.spage=46&rft.epage=68&rft.pages=46-68&rft.issn=0895-4801&rft.eissn=1095-7146&rft.coden=SJDMEC&rft_id=info:doi/10.1137/S0895480103421725&rft_dat=%3Cproquest_cross%3E2599592461%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c254t-73e5295e535a33c7dc5383e344b7ccf9961d332ce61af065f39c21d2db7715313%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=925645549&rft_id=info:pmid/&rfr_iscdi=true