Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals

DOI10.1007/978-3-319-53925-6_25zbMath1485.68321OpenAlexW2588221826MaRDI QIDQ2980919

Toshiki Saitoh, David G. Kirkpatrick

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_25

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Dominating sets in perfect graphs
• Linear time algorithms on circular-arc graphs
• Minimum dominating sets of intervals on lines
• Algorithmic graph theory and perfect graphs
• Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
• Maximum independent set for intervals by divide and conquer with pruning
• Stability in circular arc graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Independent Sets in Circular-Arc Graphs
• Priority Queues and Sorting for Read-Only Data

This page was built for publication: Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals