Refined algorithms for hitting many intervals

DOI10.1016/j.ipl.2016.11.001zbMath1393.68128OpenAlexW2551385346MaRDI QIDQ344570

Peter Damaschke

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.11.001

zbMATH Keywords

dynamic programminganalysis of algorithmsinterval graphhitting setscheduling with gaps

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (2)

Maximizing dominance in the plane and its applications ⋮ Scheduling with gaps: new models and algorithms

Cites Work

• Unnamed Item
• The maximum k-colorable subgraph problem for chordal graphs
• Linear time algorithms on circular-arc graphs
• An almost optimal algorithm for unbounded searching
• Algorithmic graph theory and perfect graphs
• On the \(k\)-coloring of intervals
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Scheduling with Gaps: New Models and Algorithms
• A threshold of ln n for approximating set cover
• Covering Analysis of the Greedy Algorithm for Partial Cover
• Algorithms for approximate string matching
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• A Greedy Heuristic for the Set-Covering Problem
• Improved Upper Bounds for Partial Vertex Cover

This page was built for publication: Refined algorithms for hitting many intervals