A supernodal formulation of vertex colouring with applications in course timetabling
From MaRDI portal
Publication:610967
DOI10.1007/s10479-010-0716-zzbMath1207.05046arXiv0710.3603OpenAlexW2087215158WikidataQ57968710 ScholiaQ57968710MaRDI QIDQ610967
Jakub Mareček, Hana Rudová, Andrew J. Parkes, Edmund Kieran Burke
Publication date: 13 December 2010
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0710.3603
Related Items (24)
Operational research in education ⋮ A new lower bound for curriculum-based course timetabling ⋮ Generating new test instances by evolving in instance space ⋮ Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem ⋮ Minimum penalty perturbation heuristics for curriculum-based timetables subject to multiple disruptions ⋮ Grouping products for the optimization of production processes: a case in the steel manufacturing industry ⋮ The minimum chromatic violation problem: a polyhedral approach ⋮ An integer programming approach to b-coloring ⋮ Fractional programming formulation for the vertex coloring problem ⋮ Variable neighborhood descent search based algorithms for course timetabling problem: application to a Tunisian university ⋮ Mobility offer allocations in corporate settings ⋮ Symmetry-breaking inequalities for ILP with structured sub-symmetry ⋮ The maximum-impact coloring polytope ⋮ Multi-coloring and job-scheduling with assignment and incompatibility costs ⋮ \textit{teaspoon}: solving the curriculum-based course timetabling problems with answer set programming ⋮ Quality recovering of university timetables ⋮ Answer set programming as a modeling language for course timetabling ⋮ Dantzig-Wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling ⋮ A column generation based algorithm for the robust graph coloring problem ⋮ Polyhedral studies of vertex coloring problems: the standard formulation ⋮ A branch-and-cut procedure for the Udine course timetabling problem ⋮ Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem ⋮ Comments on: ``An overview of curriculum-based course timetabling ⋮ An overview of curriculum-based course timetabling
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generating all the acyclic orientations of an undirected graph
- The strong perfect graph theorem
- A computational study of a cutting plane algorithm for university course timetabling
- Packing and partitioning orbitopes
- Using stable sets to bound the chromatic number
- Application of a real-world university-course timetabling model solved by integer programming
- Cliques, holes and the vertex coloring polytope
- On the system of two all different\(\_\)predicates
- Graph derivatives
- On the X-join decomposition for undirected graphs
- Weighted graphs and university course timetabling
- The complexity of comparability graph recognition and coloring
- Properties of some ILP formulations of a class of partitioning problems
- Zero knowledge and the chromatic number
- Pruning by isomorphism in branch-and-cut
- Exploiting orbits in symmetric ILP
- Recent research directions in automated timetabling
- All-different polytopes
- Two novel evolutionary formulations of the graph coloring problem
- Facets of the graph coloring polytope
- A dualistic approach to bounding the chromatic number of a graph
- A cutting plane algorithm for graph coloring
- Conflict analysis in mixed integer programming
- Symmetric ILP: Coloring and small integers
- On the asymmetric representatives formulation for the vertex coloring problem
- A survey of local search methods for graph coloring
- A branch-and-cut algorithm for graph coloring
- Neighborhood portfolio approach for local search applied to timetabling problems
- Representations of the all_different Predicate of Constraint Satisfaction in Integer Programming
- On a Binary-Encoded ILP Coloring Formulation
- A Class Representative Model for Pure Parsimony Haplotyping
- Towards improving the utilization of university teaching space
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Incremental modular decomposition
- A Combinatorial Decomposition Theory
- The Complexity of Near-Optimal Graph Coloring
- On the Application of the Minimum Degree Algorithm to Finite Element Systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- A Column Generation Approach for Graph Coloring
- Handbook of Graph Theory
- Penalising Patterns in Timetables: Novel Integer Programming Formulations
- Orbitopal Fixing
- Orbital Branching
- Transitiv orientierbare Graphen
- Nombre chromatique et plus longs chemins d'un graphe
- What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
- Models and solution techniques for frequency assignment problems
- The two possible values of the chromatic number of a random graph
This page was built for publication: A supernodal formulation of vertex colouring with applications in course timetabling
