On the Complexity of Timetable and Multicommodity Flow Problems

DOI10.1137/0205048zbMath0358.90021DBLPjournals/siamcomp/EvenIS76OpenAlexW2003160050WikidataQ30053671 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 (only showing first 100 items - show all)

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 ⋮ Finding dense subgraphs ⋮ A tight max-flow min-cut duality theorem for nonlinear multicommodity flows ⋮ 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 ⋮ On the complexity of nurse rostering problems ⋮ Graph isomorphism restricted by lists ⋮ Constrained flows in networks ⋮ 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 ⋮ Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms ⋮ Graph realization of distance sets ⋮ 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

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