The S-digraph optimization problem and the greedy algorithm

DOI10.1016/J.DISOPT.2005.08.004MaRDI QIDQ1019296zbMATH OpenOpenAlexFDO

Authors David Hartvigsen

Publication date 2 June 2009

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2005.08.004

zbMATH Keywords

greedy algorithmdata compressionmatroidsHuffman codes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• On the Greedy Solution of Ordering Problems
• An Exact Characterization of Greedy Structures
• A greedy algorithm for maximizing a linear objective function
• A class of greedy algorithms and its relation to greedoids
• scientific article; zbMATH DE number 3904604

Cites work

• scientific article; zbMATH DE number 1805583 (Why is no real title available?)
• scientific article; zbMATH DE number 3162350 (Why is no real title available?)
• scientific article; zbMATH DE number 42741 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3476581 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• A Method for the Construction of Minimum-Redundancy Codes
• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An algorithm for the detection and construction of Monge sequences
• Code and parse trees for lossless source encoding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Conditions for Optimality of the Huffman Algorithm
• Design and analysis of dynamic Huffman codes
• Dynamic huffman coding
• Greedoids
• Introduction to algorithms
• Matroids and the greedy algorithm
• Note on Independence Functions
• On the Optimality of Huffman Trees
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Optimal assignments in an ordered set: An application of matroid theory
• The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem Over a Lattice of Binary Trees
• Variations on a theme by Huffman

Cited in

(5)

• Dijkstra's algorithm and L-concave function maximization
• scientific article; zbMATH DE number 6469169 (Why is no real title available?)
• scientific article; zbMATH DE number 889960 (Why is no real title available?)
• scientific article; zbMATH DE number 176397 (Why is no real title available?)
• A class of greedy algorithms and its relation to greedoids

This page was built for publication: The \(S\)-digraph optimization problem and the greedy algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1019296)