Bounded fractionality of the multiflow feasibility problem for demand graph K_3 + K_3 and related maximization problems
Bounded fractionality of the multiflow feasibility problem for demand graph K_3 + K_3 and related maximization problems
复制标题
需求图K_3 K_3多流可行性问题的有界分数及相关最大化问题
DOI：
10.1016/j.jctb.2012.02.001
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
H. Hirai
中科院分区：
文献类型：
--
作者：
矢田和善;青嶋 誠;Y. Saiki;H. Hirai
考虑需求图为两个三角形顶点不相交并的多流可行性问题。我们表明，这个问题有1/12积分的解决方案，只要它是可行的，并满足欧拉条件。这解决了Karzanov提出的一个猜想，并完成了有界分形需求图的分类。我们把这个问题归结为多流最大化问题，其终端权重是完全二部图的图度量，并证明了它总是有一个1/12整数的最优多流的每一个内部欧拉图。
We consider the multiflow feasibility problem whose demand graph is the vertex-disjoint union of two triangles. We show that this problem has a 1/12-integral solution whenever it is feasible and satisfies the Euler condition. This solves a conjecture raised by Karzanov, and completes the classification of the demand graphs having bounded fractionality. We reduce this problem to the multiflow maximization problem whose terminal weight is the graph metric of the complete bipartite graph, and show that it always has a 1/12-integral optimal multiflow for every inner Eulerian graph.