Strip Graphs: Recognition and Scheduling

DOI10.1007/11917496_13MaRDI QIDQ3522951zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Ragnar K. Karlsson

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_13

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Interval selection with machine-dependent intervals
• Mutual exclusion scheduling with interval graphs or related classes. I
• scientific article; zbMATH DE number 2119734

Cited in

(9)

• Scheduling meets \(n\)-fold integer programming
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• Parameterized complexity of machine scheduling: 15 open problems
• Single-machine scheduling with release times, deadlines, setup times, and rejection
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• A Graphical Foundation for Schedules
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Completing partial schedules for open shop with unit processing times and routing

This page was built for publication: Strip Graphs: Recognition and Scheduling

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