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)

• Aliased register allocation for straight-line programs is NP-complete
• Recognition and dualization of disguised bidual Horn functions.
• Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
• How to pack directed acyclic graphs into small blocks
• Routing in undirected graphs with constant congestion
• A hierarchy of tractable satisfiability problems
• A multistage view on 2-satisfiability
• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
• Multicommodity network flows: a survey. I: Applications and formulations
• The subgraph homeomorphism problem
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• On the complexity of nurse rostering problems
• Algorithms Solving the Matching Cut Problem
• Classification, models and exact algorithms for multi-compartment delivery problems
• A switching algorithm for the solution of quadratic Boolean equations
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• 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?
• Two edge-disjoint paths with length constraints
• The point-to-point delivery and connection problems: Complexity and algorithms
• Tight integral duality gap in the Chinese postman problem
• Linear-Time Algorithm for Quantum 2SAT
• Scheduling sports competitions on multiple venues.
• The disjoint shortest paths problem
• Disjoint paths in sparse graphs
• Edge-disjoint odd cycles in 4-edge-connected graphs
• The complexity of finding two disjoint paths with min-max objective function
• Reduction from three-dimensional discrete tomography to multicommodity flow problem
• scientific article; zbMATH DE number 2192203 (Why is no real title available?)
• Congestion-free rerouting of flows on DAGs
• A new adjustment of the branch and price algorithm for university course timetabling
• A perspective on certain polynomial-time solvable classes of satisfiability
• Bipartite bihypergraphs: a survey and new results
• Minimal multicut and maximal integer multiflow: a survey
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Generalized partitions of graphs
• The -transportation problem: on the value of split transports for the physical internet concept
• Bisplit graphs
• Edge-coloring of 3-uniform hypergraphs
• A simplified NP-complete satisfiability problem
• A bounded approximation for the minimum cost 2-sat problem
• Improving paper spread in examination timetables using integer programming
• Detecting strong cliques
• Complete and tractable machine-independent characterizations of second-order polytime
• A stochastic local search algorithm with adaptive acceptance for high-school timetabling
• GOAL solver: a hybrid local search based solver for high school timetabling
• The undirected two disjoint shortest paths problem
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Interval edge coloring of a graph with forbidden colors
• An efficient and effective approximation algorithm for the Map Labeling Problem
• Using graphs for some discrete tomography problems
• An interactive system for constructing timetables on a PC
• Vertex disjoint paths on clique-width bounded graphs
• Autark assignments of Horn CNFs
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• Upgrading edge-disjoint paths in a ring
• Pattern matching in a digitized image
• On k-positive satisfiability problem
• The complexity of colouring problems on dense graphs
• Finding dense subgraphs
• Multiflows in symmetric digraphs
• A survey of school timetabling research
• On orientations and shortest paths
• Parallel connectivity in edge-colored complete graphs: complexity results
• The directed subgraph homeomorphism problem
• Approximate constrained bipartite edge coloring
• Edge coloring of bipartite graphs with constraints
• On the complexity of scheduling tasks with discrete starting times
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A hierarchy of propositional Horn formuls
• Preassignment requirements in chromatic scheduling
• Multicriteria movement synchronization scheduling problems and algorithms
• Complexity of one packing optimization problem
• Probabilistic bounds and algorithms for the maximum satisfiability problem
• Finding read-once resolution refutations in systems of 2CNF clauses
• Constrained flows in networks
• Recognition of q-Horn formulae in linear time
• Computing maximal autarkies with few and simple oracle queries
• Interval vertex-coloring of a graph with forbidden colors
• How to collect balls moving in the Euclidean plane
• 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
• Disjoint paths in symmetric digraphs
• A polynomial time solution for labeling a rectilinear map
• Edge-chromatic sum of trees and bounded cyclicity graphs
• On the complexity of the planar directed edge-disjoint paths problem
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• The multi-league sports scheduling problem, or how to schedule thousands of matches
• Reconstruction of two subclasses of 2L-convex polyominoes
• On the planar integer two-flow problem
• A multimaterial transport problem and its convex relaxation via rectifiable G-currents
• 2-linked graphs
• Disjoint paths in graphs
• Packing Arc-Disjoint Cycles in Tournaments
• School timetabling for quality student and teacher schedules
• School timetabling problem

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)