Models of greedy algorithms for graph problems

DOI10.1007/S00453-007-9124-4zbMath1191.68824OpenAlexW3135922541MaRDI QIDQ834580

Russell Impagliazzo, Sashka Davis

Publication date: 27 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9124-4

zbMATH Keywords

greedy algorithmspriority algorithmsgraph optimization problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Subquadratic algorithms for succinct stable matching ⋮ Advice complexity of adaptive priority algorithms ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Hybrid Bellman-Ford-Dijkstra algorithm ⋮ Greedy matching: guarantees and limitations ⋮ Limitations of incremental dynamic programming ⋮ On exponential time lower bound of Knapsack under backtracking ⋮ Unnamed Item ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Advice complexity of priority algorithms ⋮ On sum coloring and sum multi-coloring for restricted families of graphs ⋮ Priority algorithms for graph optimization problems ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toward a model for backtracking and dynamic programming
• On the hardness of approximating minimum vertex cover
• Hierarchies for classes of priority algorithms for job scheduling
• Worst-case performance of Rayward-Smith's Steiner tree heuristic
• The Steiner problem with edge lengths 1 and 2
• A fast algorithm for Steiner trees
• Approximation algorithms for combinatorial problems
• (Incremental) priority algorithms
• The power of priority algorithms for facility location and set cover
• Improved non-approximability results for minimum vertex cover with density constraints
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• The computation of nearly minimal Steiner trees in graphs
• Tighter Bounds for Graph Steiner Tree Approximation
• Approximation and Online Algorithms
• Approximation and Online Algorithms
• Automata, Languages and Programming
• Approximation and Online Algorithms

This page was built for publication: Models of greedy algorithms for graph problems