Interval scheduling and colorful independent sets

DOI10.1007/s10951-014-0398-5zbMath1328.90065arXiv1402.0851OpenAlexW3101862638MaRDI QIDQ892898

Rolf Niedermeier, Matthias Mnich, Mathias Weller, René van Bevern

Publication date: 12 November 2015

Published in: Journal of Scheduling, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0851

zbMATH Keywords

interval graphsparameterized complexity2-union graphsjob interval selectionstrip graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (26)

Balanced independent and dominating sets on colored interval graphs ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Tree Containment With Soft Polytomies ⋮ On data reduction for dynamic vector bin packing ⋮ Fixed interval scheduling with third‐party machines ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ A new perspective on single-machine scheduling problems with late work related criteria ⋮ Unnamed Item ⋮ On streaming algorithms for geometric independent set and clique ⋮ Winner determination in geometrical combinatorial auctions ⋮ Unnamed Item ⋮ Finding temporal paths under waiting time constraints ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Star Partitions of Perfect Graphs ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ Unnamed Item ⋮ Scheduling meets \(n\)-fold integer programming ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Parameterizing by the number of numbers
• Random interval graphs
• Some simplified NP-complete graph problems
• Which problems have strongly exponential complexity?
• On the approximability of an interval scheduling problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Incidence matrices and interval graphs
• Parametrized complexity theory.
• Integrated Sequencing and Scheduling in Coil Coating
• The LBFS Structure and Recognition of Interval Graphs
• Complexity results for scheduling tasks with discrete starting times
• Strip Graphs: Recognition and Scheduling
• Interval scheduling: A survey
• Limits and Applications of Group Algebras for Parameterized Problems
• On Finding the Maxima of a Set of Vectors
• Graph Classes: A Survey
• Color-coding
• Kernelization Lower Bounds by Cross-Composition
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Scheduling and Fixed-Parameter Tractability
• Scheduling Split Intervals
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

This page was built for publication: Interval scheduling and colorful independent sets