Models of greedy algorithms for graph problems

DOI10.1007/S00453-007-9124-4zbMATH Open1191.68824OpenAlexW3135922541MaRDI QIDQ834580FDOQ834580

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) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cites Work

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

Cited In (16)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• Approximation and Online Algorithms 👍 👎
• Priority algorithms for graph optimization problems 👍 👎
• The power of priority algorithms for facility location and set cover 👍 👎
• Title not available (Why is that?) 👍 👎

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

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