Interval scheduling and colorful independent sets
type: Item
instance of: scholarly article
title: Interval scheduling and colorful independent sets
title: Interval Scheduling and Colorful Independent Sets
zbMATH Open document ID: 1328.90065
zbMATH Open document ID: 1260.68167
DOI: 10.1007/978-3-642-35261-4_28
DOI: 10.1007/S10951-014-0398-5
author: René van Bevern
author: Matthias Mnich
author: Rolf Niedermeier
author: Mathias Weller
published in: Journal of Scheduling
published in: Algorithms and Computation
publication date: 2015-11-12T00:00:00Z
publication date: 2013-03-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1402.0851
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 6508013
zbMATH DE Number: 6147810
zbMATH Keywords: interval graphs
zbMATH Keywords: 2-union graphs
zbMATH Keywords: strip graphs
zbMATH Keywords: job interval selection
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
OpenAlex ID: W3101862638
OpenAlex ID: W2568515082
arXiv ID: 1402.0851
cites work: Color-coding
cites work: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
cites work: Scheduling Split Intervals
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Graph Classes: A Survey
cites work: Q2934608
cites work: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
cites work: The LBFS Structure and Recognition of Interval Graphs
cites work: Fundamentals of parameterized complexity
cites work: Parameterizing by the number of numbers
cites work: Parametrized complexity theory.
cites work: Incidence matrices and interval graphs
cites work: Some simplified NP-complete graph problems
cites work: Q3838186
cites work: Strip Graphs: Recognition and Scheduling
cites work: Integrated Sequencing and Scheduling in Coil Coating
cites work: Which problems have strongly exponential complexity?
cites work: On the parameterized complexity of some optimization problems related to multiple-interval graphs
cites work: Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
cites work: Interval scheduling: A survey
cites work: Limits and Applications of Group Algebras for Parameterized Problems
cites work: Q4967164
cites work: On Finding the Maxima of a Set of Vectors
cites work: Q4904144
cites work: Scheduling and Fixed-Parameter Tractability
cites work: Complexity results for scheduling tasks with discrete starting times
cites work: Q5710169
cites work: Random interval graphs
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: On the approximability of an interval scheduling problem
Recommended article: Interval colorings of graphs—Coordinated and unstable no‐wait schedules
Recommended article: A note to independent sets in scheduling
Recommended article: Extensions of coloring models for scheduling purposes
Recommended article: Q2712373
Recommended article: Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules
Recommended article: Q5111006
Recommended article: Scheduling Problems and Mixed Graph Colorings
Recommended article: Interval edge-coloring: A model of curriculum scheduling
description: scientific article; zbMATH DE number 6147810
alternative label: Interval Scheduling and Colorful Independent Sets