<p>Discrete <i>p</i>-modulus is a generalization of several graph theoretic quantities—including max flow, min cut, shortest path, and effective resistance—to families of objects on graphs. The modulus problem has several formulations as a convex optimization problem, all of which share the feature that each object in the family induces a constraint. Thus, the modulus problem generally has the form of a convex optimization problem with a finite but large set of constraints that often cannot even be enumerated in a reasonable amount of time. Previous results have demonstrated that the modulus of different families can be used to explore different structural features of a graph. However, only a few such families (paths, cycles, and spanning trees) have been studied in depth. This paper initiates the exploration of the modulus of edge covers, establishing theoretical results and demonstrating, by numerical experiments, some interesting behaviors of this modulus. On large graphs, the modulus of edge covers can be computationally challenging due to the number of constraints. This is addressed by relating the edge covers to the larger family of fractional edge covers. The modulus of the latter family can be computed efficiently using a duality result connecting fractional edge covers to the much smaller family of stars.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Modulus of Edge Covers and Stars

  • Adriana Ortiz-Aquino,
  • Nathan Albin

摘要

Discrete p-modulus is a generalization of several graph theoretic quantities—including max flow, min cut, shortest path, and effective resistance—to families of objects on graphs. The modulus problem has several formulations as a convex optimization problem, all of which share the feature that each object in the family induces a constraint. Thus, the modulus problem generally has the form of a convex optimization problem with a finite but large set of constraints that often cannot even be enumerated in a reasonable amount of time. Previous results have demonstrated that the modulus of different families can be used to explore different structural features of a graph. However, only a few such families (paths, cycles, and spanning trees) have been studied in depth. This paper initiates the exploration of the modulus of edge covers, establishing theoretical results and demonstrating, by numerical experiments, some interesting behaviors of this modulus. On large graphs, the modulus of edge covers can be computationally challenging due to the number of constraints. This is addressed by relating the edge covers to the larger family of fractional edge covers. The modulus of the latter family can be computed efficiently using a duality result connecting fractional edge covers to the much smaller family of stars.