On the Complexity of Timetable and Multicommodity Flow Problems

DOI10.1137/0205048zbMATH Open0358.90021DBLPjournals/siamcomp/EvenIS76OpenAlexW2003160050WikidataQ30053671 ScholiaQ30053671MaRDI QIDQ4132234FDOQ4132234

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Cited In (only showing first 100 items - show all)

Classification, models and exact algorithms for multi-compartment delivery problems
The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree
Title not available (Why is that?)
Edge-disjoint odd cycles in 4-edge-connected graphs
The complexity of finding two disjoint paths with min-max objective function
Bipartite bihypergraphs: a survey and new results
Bisplit graphs
Minimal multicut and maximal integer multiflow: a survey
A bounded approximation for the minimum cost 2-sat problem
Edge-coloring of 3-uniform hypergraphs
A simplified NP-complete satisfiability problem
The undirected two disjoint shortest paths problem
A stochastic local search algorithm with adaptive acceptance for high-school timetabling
GOAL solver: a hybrid local search based solver for high school timetabling
Probabilistic construction of deterministic algorithms: approximating packing integer programs
Using graphs for some discrete tomography problems
On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
Upgrading edge-disjoint paths in a ring
The complexity of colouring problems on dense graphs
On orientations and shortest paths
A survey of school timetabling research
The directed subgraph homeomorphism problem
A linear-time algorithm for testing the truth of certain quantified Boolean formulas
Probabilistic bounds and algorithms for the maximum satisfiability problem
Complexity of one packing optimization problem
Recognition of \(q\)-Horn formulae in linear time
A polynomial time solution for labeling a rectilinear map
Edge-chromatic sum of trees and bounded cyclicity graphs
Decision lists and related Boolean functions
2-linked graphs
Disjoint paths in graphs
The Induced Disjoint Paths Problem
School timetabling for quality student and teacher schedules
Reconstructing \(hv\)-convex polyominoes from orthogonal projections
Generalized \(p\)-center problems: Complexity results and approximation algorithms
On a multiconstrained model for chromatic scheduling
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Recognition of unipolar and generalised split graphs
Finding a feasible course schedule using Tabu search
Half-integral five-terminus flows
The combinatorics of timetabling
On the use of graphs in discrete tomography
Network flow and 2-satisfiability
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
A minimum cost network flow model for the maximum covering and patrol routing problem
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
Minimum-diameter covering problems
Optimal product design using conjoint analysis: Computational complexity and algorithms
A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem
Monte Carlo hyper-heuristics for examination timetabling
Strong bounds with cut and column generation for class-teacher timetabling
An introduction to timetabling
On the complexity of manpower shift scheduling
On computing minimal models
Digraph width measures in parameterized algorithmics
Boundary properties of the satisfiability problems
The \(Multi\)-SAT algorithm
Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem
Mathematical models and algorithms for a high school timetabling problem
Variable neighborhood search based algorithms for high school timetabling
Finding disjoint paths with related path costs
Fixed interval scheduling: models, applications, computational complexity and algorithms
Extensions of coloring models for scheduling purposes
Complexity of a 3-dimensional assignment problem
Primal-dual approximation algorithms for integral flow and multicut in trees
A tabu search algorithm for computing an operational timetable
Decomposition, reformulation, and diving in university course timetabling
A linear algorithm for renaming a set of clauses as a Horn set
Timetabling problems at the TU Eindhoven
Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems
Multiflows and disjoint paths of minimum total cost
Towards constraint-based school timetabling
A survey of metaheuristic-based techniques for university timetabling problems
Disjoint paths in graphs. (Reprint)
Polynomial reduction of time-space scheduling to time scheduling
Restricted coloring models for timetabling
A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem.
LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
Induced disjoint paths problem in a planar digraph
Complexity of some special types of timetabling problems
A kernel of order \(2k - c\) for Vertex Cover
Integer programming techniques for educational timetabling
Algorithms for the maximum satisfiability problem
Redundancy in logic. II: 2CNF and Horn propositional formulae
Combining column generation and constraint programming to solve the tail assignment problem
Finding Two Edge-Disjoint Paths with Length Constraints
NP-completeness of some edge-disjoint paths problems
Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
A hierarchy of tractable satisfiability problems
The subgraph homeomorphism problem
Approximating a generalization of MAX 2SAT and MIN 2SAT
Efficient branch-and-bound algorithms for weighted MAX-2-SAT
Uniquely solvable quadratic Boolean equations
Integer equal flows
Is intractability of nonmonotonic reasoning a real drawback?
The point-to-point delivery and connection problems: Complexity and algorithms
Tight integral duality gap in the Chinese postman problem
Scheduling sports competitions on multiple venues.
The disjoint shortest paths problem
A perspective on certain polynomial-time solvable classes of satisfiability

This page was built for publication: On the Complexity of Timetable and Multicommodity Flow Problems

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