On the Complexity of Timetable and Multicommodity Flow Problems

DOI10.1137/0205048zbMath0358.90021OpenAlexW2003160050WikidataQ30053671 ScholiaQ30053671MaRDI QIDQ4132234

Adi Shamir, Alon Itai, Shimon Even

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/97f74136151895212c16e98f020796e037cf1a45

Mathematics Subject Classification ID

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

Related Items

INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES, Multicriteria movement synchronization scheduling problems and algorithms, Computing Maximal Autarkies with Few and Simple Oracle Queries, Unnamed Item, Finding Two Edge-Disjoint Paths with Length Constraints, Optimization in telecommunication networks, Unnamed Item, Angle Covers: Algorithms and Complexity, Congestion-Free Rerouting of Flows on DAGs, All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs, Algorithms Solving the Matching Cut Problem, INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES, Defragmentation of permutation tables with four columns, On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems, The Induced Disjoint Paths Problem, An efficient and effective approximation algorithm for the Map Labeling Problem, A quest for a fair schedule: the international Young Physicists' Tournament, An approximation algorithm for 3-Colourability, Concurrent flows and packet routing in Cayley graphs (Preliminary version), Parallel connectivity in edge-colored complete graphs: complexity results, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, Unnamed Item, Unnamed Item, Online interval scheduling with predictions, Almost disjoint paths and separating by forbidden pairs, Filling crosswords is very hard, A multistage view on 2-satisfiability, Unnamed Item, Multiflow Feasibility: An Annotated Tableau, Unnamed Item, On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas, No-Wait Scheduling for Locks, Computing $k$-Atomicity in Polynomial Time, Unnamed Item, Programação da grade de horário em escolas de ensino fundamental e médio, RECONSTRUCTION OF TWO SUBCLASSES OF 2L-CONVEX POLYOMINOES, On the use of graphs in discrete tomography, On the use of graphs in discrete tomography, Timetabling problems at the TU Eindhoven, Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem, Linear-Time Algorithm for Quantum 2SAT, Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms, Minimum-diameter covering problems, Workface planning in synchronous production systems, Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees, The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree, Unnamed Item, Edge coloring of bipartite graphs with constraints, Decision lists and related Boolean functions, Random 2-SAT: Results and problems, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Graph isomorphism restricted by lists, Minimum-cost strong network orientation problems: Classification, complexity, and algorithms, Disjoint paths and connected subgraphs for \(H\)-free graphs, Disjoint paths and connected subgraphs for \(H\)-free graphs, Level-planar drawings with few slopes, Unnamed Item, CASCADING RANDOM WALKS, Routing in Undirected Graphs with Constant Congestion, NP-Complete operations research problems and approximation algorithms, New Hardness Results for Routing on Disjoint Paths, Packing Arc-Disjoint Cycles in Tournaments, A Multimaterial Transport Problem and its Convex Relaxation via Rectifiable $G$-currents, Unnamed Item, Unnamed Item, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, Integral decomposition in polyhedra, Variations on Instant Insanity, Unnamed Item, OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS, Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs, The complexity of colouring problems on dense graphs, Edge-disjoint odd cycles in 4-edge-connected graphs, GOAL solver: a hybrid local search based solver for high school timetabling, A stochastic local search algorithm with adaptive acceptance for high-school timetabling, Complexity of one packing optimization problem, Integer equal flows, A polynomial time solution for labeling a rectilinear map, Edge-chromatic sum of trees and bounded cyclicity graphs, School timetabling for quality student and teacher schedules, Combining column generation and constraint programming to solve the tail assignment problem, A minimum cost network flow model for the maximum covering and patrol routing problem, Improving paper spread in examination timetables using integer programming, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Variable neighborhood search based algorithms for high school timetabling, Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem, Finding disjoint paths with related path costs, Mathematical models and algorithms for a high school timetabling problem, A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem, Fixed interval scheduling: models, applications, computational complexity and algorithms, How to collect balls moving in the Euclidean plane, LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Optimal product design using conjoint analysis: Computational complexity and algorithms, An interactive system for constructing timetables on a PC, ATM VP-based network design, On fractional multicommodity flows and distance functions, A hierarchy of propositional Horn formuls, A generalization of interval edge-colorings of graphs, On orientations and shortest paths, The directed subgraph homeomorphism problem, The subgraph homeomorphism problem, An algorithm for imbedding cubic graphs in the torus, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, The Rabin index of parity games: its complexity and approximation, Algorithms solving the matching cut problem, Disjoint paths in graphs, 2-linked graphs, Upgrading edge-disjoint paths in a ring, Trichotomy for integer linear systems based on their sign patterns, A switching algorithm for the solution of quadratic Boolean equations, Chromatic optimisation: Limitations, objectives, uses, references, Probabilistic bounds and algorithms for the maximum satisfiability problem, Tree metrics and edge-disjoint \(S\)-paths, A survey of school timetabling research, The inequality-satisfiability problem, Finding disjoint paths in split graphs, Some results concerning the complexity of restricted colorings of graphs, Modelling and solving an acyclic multi-period timetabling problem, Finding a feasible course schedule using Tabu search, Parameterized complexity analysis for the closest string with wildcards problem, The interval constrained 3-coloring problem, Primal-dual approximation algorithms for integral flow and multicut in trees, A bounded approximation for the minimum cost 2-sat problem, Compatible 2-factors, The point-to-point delivery and connection problems: Complexity and algorithms, A logic approach to the resolution of constraints in timetabling, On the reconstruction of binary and permutation matrices under (binary) tomographic constraints, On the complexity of scheduling tasks with discrete starting times, Tight integral duality gap in the Chinese postman problem, Aliased register allocation for straight-line programs is NP-complete, On the integral plane two-commodity flow problem, An efficient algorithm for the 3-satisfiability problem, Multicommodity flow in trees: packing via covering and iterated relaxation, The logic of constraint satisfaction, A kernel of order \(2k - c\) for Vertex Cover, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, A hierarchy of tractable satisfiability problems, Induced disjoint paths problem in a planar digraph, Disjoint paths in sparse graphs, Minimal multicut and maximal integer multiflow: a survey, Multiflows in symmetric digraphs, Rainbow graph splitting, On the hardness of finding near-optimal multicuts in directed acyclic graphs, Half-integral five-terminus flows, An assignment problem and its application in education domain: a review and potential path, The complexity of finding two disjoint paths with min-max objective function, On the planar integer two-flow problem, Efficient algorithms for generalized stable marriage and roommates problems, Edge-coloring of 3-uniform hypergraphs, Disjoint paths in symmetric digraphs, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Solving partition problems with colour-bipartitions, Extensions of coloring models for scheduling purposes, Algorithms for the maximum satisfiability problem, Connectivity vs. reachability, An introduction to timetabling, Combinatorial optimization in system configuration design, Polynomial reduction of time-space scheduling to time scheduling, Edges and switches, tunnels and bridges, Generalized \(p\)-center problems: Complexity results and approximation algorithms, The combinatorics of timetabling, Condensing timetables with target date divisible by each instructor's number of class hours, Generalized partitions of graphs, Decomposition, reformulation, and diving in university course timetabling, Nash equilibria in all-optical networks, On a multiconstrained model for chromatic scheduling, A simplified NP-complete satisfiability problem, Interval edge coloring of a graph with forbidden colors, Packing paths in planar graphs, Uniquely solvable quadratic Boolean equations, The complexity of propositional closed world reasoning and circumscription, A tabu search algorithm for computing an operational timetable, An efficiently solvable graph partition problem to which many problems are reducible, Pattern matching in a digitized image, Recognition of \(q\)-Horn formulae in linear time, Approximate constrained bipartite edge coloring, Classification, models and exact algorithms for multi-compartment delivery problems, Single bend wiring on surfaces, NP-completeness of some edge-disjoint paths problems, A rational reconstruction of nonmonotonic truth maintenance systems, On-line 2-satisfiability, Restricted coloring models for timetabling, Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems, The maximum integer multiterminal flow problem in directed graphs, Redundancy in logic. II: 2CNF and Horn propositional formulae, Preassignment requirements in chromatic scheduling, On the complexity of manpower shift scheduling, A polynomial time approximation algorithm for the two-commodity splittable flow problem, Open shop scheduling with some additional constraints, Multiflows and disjoint paths of minimum total cost, Maximum flow under proportional delay constraint, The terminal-pairability problem in complete bipartite graphs, Restrictions and preassignments in preemptive open shop scheduling, Packing arc-disjoint cycles in tournaments, On computing minimal models, The complexity of minimum partial truth assignments and implication in negation-free formulae, The commodity-split multi-compartment capacitated arc routing problem, Simple undirected two-commodity integral flow with a unitary demand, Is intractability of nonmonotonic reasoning a real drawback?, The disjoint shortest paths problem, Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs, Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms, The complete set of minimal simple graphs that support unsatisfiable 2-CNFs, Gene tree reconciliation including transfers with replacement is NP-hard and FPT, Jointly stable matchings, Semantics and complexity of abduction from default theories, Problem of groupage cargo routing in the multicommodity transport network with given tariffs and delivery time constraints, Matheuristics for optimizing the network in German wagonload traffic, Complexity and algorithms for recognizing polar and monopolar graphs, How to pack directed acyclic graphs into small blocks, A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem., Digraph width measures in parameterized algorithmics, Maximum renamable Horn sub-CNFs, The \(Multi\)-SAT algorithm, On complexity, representation and approximation of integral multicommodity flows, On \(k\)-positive satisfiability problem, Boundary properties of the satisfiability problems, Monotonizing linear programs with up to two nonzeroes per column, Recognition of unipolar and generalised split graphs, A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter, Autark assignments of Horn CNFs, The multi-league sports scheduling problem, or how to schedule thousands of matches, Towards constraint-based school timetabling, Finding read-once resolution refutations in systems of 2CNF clauses, Modeling elements and solving techniques for the data dissemination problem, Integer programming techniques for educational timetabling, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, A survey of metaheuristic-based techniques for university timetabling problems, Polyhedral combinatorics of multi-index axial transportation problems, A practical map labeling algorithm., Monte Carlo hyper-heuristics for examination timetabling, Strong bounds with cut and column generation for class-teacher timetabling, On the performance of scatter search for post-enrolment course timetabling problems, Scheduling in switching networks with set-up delays, Bipartite bihypergraphs: a survey and new results, Solving the resolution-free SAT problem by submodel propagation in linear time, Disjoint paths in graphs. (Reprint), Routing with congestion in acyclic digraphs, A particular timetable problem: Terminal scheduling, Vertex disjoint paths on clique-width bounded graphs, Counting the number of solutions for instances of satisfiability, Solving a real constraint satisfaction model for the university course timetabling problem: a case study, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Paired threshold graphs, The undirected two disjoint shortest paths problem, Scheduling sports competitions on multiple venues., On width measures and topological problems on semi-complete digraphs, Detecting strong cliques, On the r,s-SAT satisfiability problem and a conjecture of Tovey, Interval vertex-coloring of a graph with forbidden colors, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, Complexity of a 3-dimensional assignment problem, Two edge-disjoint paths with length constraints, Bisplit graphs, Approximating a generalization of MAX 2SAT and MIN 2SAT, A generalized class-teacher model for some timetabling problems, Recognition and dualization of disguised bidual Horn functions., Reduction from three-dimensional discrete tomography to multicommodity flow problem, Using graphs for some discrete tomography problems, On the complexity of the planar directed edge-disjoint paths problem, Complexity of some special types of timetabling problems, A fast algorithm for maximum integral two-commodity flow in planar graphs, A perspective on certain polynomial-time solvable classes of satisfiability, Disconnectivity and relative positions in simultaneous embeddings, Network flow and 2-satisfiability, A linear algorithm for renaming a set of clauses as a Horn set, Reconstructing \(hv\)-convex polyominoes from orthogonal projections, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, On interval \(\Delta\)-coloring of bipartite graphs, Two results in negation-free logic