On the Complexity of Timetable and Multicommodity Flow Problems

DOI10.1137/0205048MaRDI QIDQ4132234zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Shimon Even, Alon Itai, Adi Shamir

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 network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Cited in

(only showing first 100 items - show all)

• Tree metrics and edge-disjoint \(S\)-paths
• Multicommodity network flows: a survey. I: Applications and formulations
• Scheduling in switching networks with set-up delays
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Uniquely solvable quadratic Boolean equations
• Finding disjoint paths in split graphs
• On complexity, representation and approximation of integral multicommodity flows
• Parameterized complexity analysis for the closest string with wildcards problem
• Maximum renamable Horn sub-CNFs
• On the complexity of scheduling tasks with discrete starting times
• Pattern matching in a digitized image
• On the planar integer two-flow problem
• Solving partition problems with colour-bipartitions
• Integer equal flows
• Generalized partitions of graphs
• The maximum integer multiterminal flow problem in directed graphs
• Scheduling sports competitions on multiple venues.
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• A rational reconstruction of nonmonotonic truth maintenance systems
• A multimaterial transport problem and its convex relaxation via rectifiable \(G\)-currents
• Angle covers: algorithms and complexity
• Is intractability of nonmonotonic reasoning a real drawback?
• Semantics and complexity of abduction from default theories
• Monotonizing linear programs with up to two nonzeroes per column
• Connectivity vs. reachability
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
• Efficient algorithms for generalized stable marriage and roommates problems
• Counting the number of solutions for instances of satisfiability
• An efficiently solvable graph partition problem to which many problems are reducible
• An efficient algorithm for the 3-satisfiability problem
• Chromatic optimisation: Limitations, objectives, uses, references
• Multiflow Feasibility: An Annotated Tableau
• Random 2-SAT: Results and problems
• On the complexity of the planar directed edge-disjoint paths problem
• Vertex disjoint paths on clique-width bounded graphs
• Finding dense subgraphs
• Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
• A generalized class-teacher model for some timetabling problems
• A generalization of interval edge-colorings of graphs
• The disjoint shortest paths problem
• A hierarchy of tractable satisfiability problems
• Disjoint paths in symmetric digraphs
• Multiflows 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
• An algorithm for imbedding cubic graphs in the torus
• Packing paths in planar graphs
• The complexity of propositional closed world reasoning and circumscription
• A perspective on certain polynomial-time solvable classes of satisfiability
• Integral decomposition in polyhedra
• New hardness results for routing on disjoint paths
• On the use of graphs in discrete tomography
• Optimization in telecommunication networks
• Some results concerning the complexity of restricted colorings of graphs
• Improving paper spread in examination timetables using integer programming
• The logic of constraint satisfaction
• The subgraph homeomorphism problem
• On fractional multicommodity flows and distance functions
• The multi-league sports scheduling problem, or how to schedule thousands of matches
• Computing maximal autarkies with few and simple oracle queries
• The interval constrained 3-coloring problem
• Multicommodity flow in trees: packing via covering and iterated relaxation
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• The point-to-point delivery and connection problems: Complexity and algorithms
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• A tier-based typed programming language characterizing feasible functionals
• ATM VP-based network design
• Tight integral duality gap in the Chinese postman problem
• Recognition and dualization of disguised bidual Horn functions.
• Bisplit graphs
• Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
• Recognition of unipolar and generalised split graphs
• Disjoint paths in graphs. (Reprint)
• Decision lists and related Boolean functions
• 2-linked graphs
• Disjoint paths in graphs
• Edge-disjoint odd cycles in 4-edge-connected graphs
• Recognition of \(q\)-Horn formulae in linear time
• Generalized \(p\)-center problems: Complexity results and approximation algorithms
• Extensions of coloring models for scheduling purposes
• Complexity of a 3-dimensional assignment problem
• A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem.
• On the use of graphs in discrete tomography
• Integer programming techniques for educational timetabling
• Minimal multicut and maximal integer multiflow: a survey
• On a multiconstrained model for chromatic scheduling
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Algorithms for the maximum satisfiability problem
• On computing minimal models
• The Induced Disjoint Paths Problem
• Network flow and 2-satisfiability
• A stochastic local search algorithm with adaptive acceptance for high-school timetabling
• GOAL solver: a hybrid local search based solver for high school timetabling
• Minimum-diameter covering problems
• School timetabling for quality student and teacher schedules
• Upgrading edge-disjoint paths in a ring
• The complexity of finding two disjoint paths with min-max objective function
• Probabilistic construction of deterministic algorithms: approximating packing integer programs

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)