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)

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
Generalized partitions of graphs
Improving paper spread in examination timetables using integer programming
Finding dense subgraphs
Vertex disjoint paths on clique-width bounded graphs
Pattern matching in a digitized image
Multiflows in symmetric digraphs
On the complexity of scheduling tasks with discrete starting times
On the complexity of the planar directed edge-disjoint paths problem
Disjoint paths in symmetric digraphs
On the hardness of finding near-optimal multicuts in directed acyclic graphs
Rainbow graph splitting
An assignment problem and its application in education domain: a review and potential path
The multi-league sports scheduling problem, or how to schedule thousands of matches
A fast algorithm for maximum integral two-commodity flow in planar graphs
On the planar integer two-flow problem
A generalized class-teacher model for some timetabling problems
An efficiently solvable graph partition problem to which many problems are reducible
ATM VP-based network design
Maximum renamable Horn sub-CNFs
An efficient algorithm for the 3-satisfiability problem
Integral decomposition in polyhedra
A rational reconstruction of nonmonotonic truth maintenance systems
Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
A generalization of interval edge-colorings of graphs
On complexity, representation and approximation of integral multicommodity flows
Tree metrics and edge-disjoint $S$-paths
Solving partition problems with colour-bipartitions
On the r,s-SAT satisfiability problem and a conjecture of Tovey
Counting the number of solutions for instances of satisfiability
Connectivity vs. reachability
Chromatic optimisation: Limitations, objectives, uses, references
Packing paths in planar graphs
Angle Covers: Algorithms and Complexity
Title not available (Why is that?)
Random 2-SAT: Results and problems
New Hardness Results for Routing on Disjoint Paths
Computing Maximal Autarkies with Few and Simple Oracle Queries
Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
On the use of graphs in discrete tomography
An algorithm for imbedding cubic graphs in the torus
Optimization in telecommunication networks
Scheduling in switching networks with set-up delays
Finding disjoint paths in split graphs
Parameterized complexity analysis for the closest string with wildcards problem
The maximum integer multiterminal flow problem in directed graphs
Semantics and complexity of abduction from default theories
Multiflow Feasibility: An Annotated Tableau
Some results concerning the complexity of restricted colorings of graphs
The interval constrained 3-coloring problem
Monotonizing linear programs with up to two nonzeroes per column
Efficient algorithms for generalized stable marriage and roommates problems
The logic of constraint satisfaction
Title not available (Why is that?)
The complexity of propositional closed world reasoning and circumscription
A Multimaterial Transport Problem and its Convex Relaxation via Rectifiable $G$-currents
On fractional multicommodity flows and distance functions
Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
Multicommodity flow in trees: packing via covering and iterated relaxation
Recognition and dualization of disguised bidual Horn functions.
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

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)