Refined algorithms for hitting many intervals

DOI10.1016/J.IPL.2016.11.001MaRDI QIDQ344570zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 4197287
• Scheduling with gaps: new models and algorithms
• Efficient algorithms for finding maximum cliques of an overlap graph
• scientific article; zbMATH DE number 3892606
• Demand hitting and covering of intervals

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Algorithmic graph theory and perfect graphs
• Algorithms for approximate string matching
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• An almost optimal algorithm for unbounded searching
• Covering analysis of the greedy algorithm for partial cover
• Improved Upper Bounds for Partial Vertex Cover
• Linear time algorithms on circular-arc graphs
• On the \(k\)-coloring of intervals
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Scheduling with gaps: new models and algorithms
• The maximum k-colorable subgraph problem for chordal graphs

Cited in

(4)

• Demand hitting and covering of intervals
• Maximizing dominance in the plane and its applications
• Scheduling dyadic intervals
• Scheduling with gaps: new models and algorithms

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

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