On the geometry of graphs with a forbidden minor
On the geometry of graphs with a forbidden minor
复制标题
关于带有禁止次要图的几何
DOI：
10.1145/1536414.1536450
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
James R. Lee;Anastasios Sidiropoulos
我们研究了通过随机嵌入图的拓扑简化，最终导致减少Gupta-Newman-Rabinovich-Sinclair（GNRS）L1嵌入猜想到一对明显更简单的映射。GNRS猜想刻画了所有具有O（1）-近似多商品最大流/最小割定理的图。特别是，它的决议将意味着一个常数因子近似的一般Sparling-Cut问题，在每一个家庭的图，其中禁止一些小的。在我们的研究过程中，我们证明了一些结果的独立利益。
We study the topological simplification of graphs via random embeddings, leading ultimately to a reduction of the Gupta-Newman-Rabinovich-Sinclair (GNRS) L1 embedding conjecture to a pair of manifestly simpler conjectures. The GNRS conjecture characterizes all graphs that have an O(1)-approximate multi-commodity max-flow/min-cut theorem. In particular, its resolution would imply a constant factor approximation for the general Sparsest Cut problem in every family of graphs which forbids some minor. In the course of our study, we prove a number of results of independent interest.