Shiftable intervals

DOI10.1007/s10479-006-0161-1zbMath1144.90500OpenAlexW3192861253MaRDI QIDQ2480206

Federico Malucelli, Sara Nicoloso

Publication date: 31 March 2008

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-006-0161-1

zbMATH Keywords

complexityoptimization problemsinterval graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• A unified approach to domination problems on interval graphs
• Dominating Sets in Chordal Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Two-Processor Scheduling with Start-Times and Deadlines
• A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
• Complexity and algorithms for reasoning about time
• A Characterization of Comparability Graphs and of Interval Graphs