Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review

DOI10.1007/s10951-018-0595-8zbMath1425.90039arXiv1712.06481OpenAlexW3103944330MaRDI QIDQ2327955

Matthias Bentert, René van Bevern, Rolf Niedermeier

Publication date: 8 October 2019

Published in: Journal of Scheduling (Search for Journal in Brave)

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

zbMATH Keywords

independent setchordal graphsinterval graphsNP-hard problemsparameterized complexityjob interval selectioninductive \(k\)-independent graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) 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)

Related Items (11)

Mathematical Programming Models and Exact Algorithms ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Fixed interval scheduling with third‐party machines ⋮ Equitable scheduling on a single machine ⋮ Literature reviews in operations research: a new taxonomy and a meta review ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Unnamed Item ⋮ Finding temporal paths under waiting time constraints ⋮ Computing inductive vertex orderings ⋮ Finding Temporal Paths Under Waiting Time Constraints.

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Correlation clustering
• Recognizing graphs with fixed interval number is NP-complete
• On rigid circuit graphs
• Maximizing weighted number of just-in-time jobs on unrelated parallel machines
• Interval scheduling and colorful independent sets
• On the parameterized complexity of multiple-interval graph problems
• Mutual exclusion scheduling with interval graphs or related classes. I
• Scheduling jobs with fixed start and end times
• The maximum k-colorable subgraph problem for chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Mutual exclusion scheduling
• Parameterized complexity of machine scheduling: 15 open problems
• Cluster graph modification problems
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Tolerance intersection graphs on binary trees with constant tolerance 3
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Parametrized complexity theory.
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• New Races in Parameterized Algorithmics
• How Well Can Graphs Represent Wireless Interference?
• Integrated Sequencing and Scheduling in Coil Coating
• The LBFS Structure and Recognition of Interval Graphs
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Elimination graphs
• Complexity results for scheduling tasks with discrete starting times
• Strip Graphs: Recognition and Scheduling
• Interval scheduling: A survey
• Approximation Algorithms for Intersection Graphs
• Scheduling Interval-Ordered Tasks
• Algorithmic Aspects of Vertex Elimination on Graphs
• Color-coding
• Line Graphs of Helly Hypergraphs
• Parameterized Algorithms

This page was built for publication: Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review