Article

On the complexity of time table and multi-commodity flow problems

Authors:

S. Even,

A. Itai,

A. ShamirAuthors Info & Claims

SFCS '75: Proceedings of the 16th Annual Symposium on Foundations of Computer Science

Pages 184 - 193

https://doi.org/10.1109/SFCS.1975.21

Published: 13 October 1975 Publication History

Publisher Site

Abstract

A very primitive version of Gotlieb's timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multi-commodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases. Finally, the two commodity real flow problem in undirected graphs is shown to be solvable in polynomial time. The time bound is O(|v|2|E|).

Cited By

View all

Anderson TBelay AChowdhury MCidon AZhang I(2023)Treehouse: A Case For Carbon-Aware Datacenter SoftwareACM SIGEnergy Energy Informatics Review10.1145/3630614.36306263:3(64-70)Online publication date: 25-Oct-2023
https://dl.acm.org/doi/10.1145/3630614.3630626
Zeng YZhang JLiu ZYang Y(2023)Entanglement Management through Swapping over Quantum InternetsACM SIGMETRICS Performance Evaluation Review10.1145/3626570.362659551:2(69-71)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3626570.3626595
Nance-Hall MBarford PFoerster KDurairajan R(2023)Improving Scalability in Traffic Engineering via Optical Topology ProgrammingIEEE Transactions on Network and Service Management10.1109/TNSM.2023.333589821:2(1581-1600)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3335898
Show More Cited By

On the complexity of time table and multi-commodity flow problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in Dist NP under the hypothesis that P NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different ...
Low-Step Multi-commodity Flow Emulators
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous ...
Exploring the Subexponential Complexity of Completion Problems

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced subgraph. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SFCS '75: Proceedings of the 16th Annual Symposium on Foundations of Computer Science

October 1975

193 pages

Publisher

IEEE Computer Society

United States

Publication History

Published: 13 October 1975

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Anderson TBelay AChowdhury MCidon AZhang I(2023)Treehouse: A Case For Carbon-Aware Datacenter SoftwareACM SIGEnergy Energy Informatics Review10.1145/3630614.36306263:3(64-70)Online publication date: 25-Oct-2023
https://dl.acm.org/doi/10.1145/3630614.3630626
Zeng YZhang JLiu ZYang Y(2023)Entanglement Management through Swapping over Quantum InternetsACM SIGMETRICS Performance Evaluation Review10.1145/3626570.362659551:2(69-71)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3626570.3626595
Nance-Hall MBarford PFoerster KDurairajan R(2023)Improving Scalability in Traffic Engineering via Optical Topology ProgrammingIEEE Transactions on Network and Service Management10.1109/TNSM.2023.333589821:2(1581-1600)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3335898
Radermacher MRutter I(2022)Inserting an edge into a geometric embeddingComputational Geometry: Theory and Applications10.1016/j.comgeo.2021.101843102:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.comgeo.2021.101843
Santos ARizk ASteinke F(2020)Flexible Redundancy Generation for Virtual Network Embedding with an Application to Smart GridsProceedings of the Eleventh ACM International Conference on Future Energy Systems10.1145/3396851.3397693(97-105)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3396851.3397693
Tan HJiang SLi YLi XZhang CHan ZLau F(2019)Joint Online Coflow Routing and Scheduling in Data Center NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2019.293072127:5(1771-1786)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2930721
Trimponias GXiao YWu XXu HGeng Y(2019)Node-Constrained Traffic EngineeringIEEE/ACM Transactions on Networking10.1109/TNET.2019.292158927:4(1344-1358)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2921589
Lan SFan WLiu TYang S(2019)A hybrid SCA–VNS meta-heuristic based on Iterated Hungarian algorithm for physicians and medical staff scheduling problem in outpatient department of large hospitals with multiple branchesApplied Soft Computing10.1016/j.asoc.2019.10581385:COnline publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.105813
Schmitz HLykourentzou I(2018)Online Sequencing of Non-Decomposable Macrotasks in Expert CrowdsourcingACM Transactions on Social Computing10.1145/31404591:1(1-33)Online publication date: 10-Jan-2018
https://dl.acm.org/doi/10.1145/3140459
Fleszar KMnich MSpoerhase J(2018)New algorithms for maximum disjoint paths based on tree-likenessMathematical Programming: Series A and B10.1007/s10107-017-1199-3171:1-2(433-461)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10107-017-1199-3
Show More Cited By

Abstract

Cited By

Recommendations

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

Low-Step Multi-commodity Flow Emulators

Exploring the Subexponential Complexity of Completion Problems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations