
doi: 10.1007/11751595_78
Given an edge-capacitated graph and kterminal vertices, the maximum integer multiterminal flow problem (MaxIMTF) is to route the maximum number of flow units between the terminals. For directed graphs, we introduce a new parameter kL ≤ k and prove that MaxIMTF is $\mathcal{NP}$-hard when k = kL = 2 and when kL = 1 and k = 3, and polynomial-time solvable when kL = 0 and when kL = 1 and k = 2. We also give an 2 log2 (kL + 2)-approximation algorithm for the general case. For undirected graphs, we give a family of valid inequalities for MaxIMTF that has several interesting consequences, and show a correspondence with valid inequalities known for MaxIMTF and for the associated minimum multiterminal cut problem.
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO] Computer Science [cs]
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO] Computer Science [cs]
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
