Blocking duality for p-modulus on networks and applications
Albin, Nathan Clemens, Jason R. Fernando, Nethali Poggi-Corradini, Pietro
Albin, Nathan
Clemens, Jason R.
Fernando, Nethali
Poggi-Corradini, Pietro
Citations
Altmetric:
Other Names
Location
Time Period
Advisors
Original Date
Digitization Date
Issue Date
2019-06
Type
Article
Genre
Keywords
p-Modulus,Blocking duality,Effective resistance,Randomly weighted graphs
Subjects (LCSH)
Citation
Albin, N., Clemens, J., Fernando, N. et al. Annali di Matematica (2019) 198: 973
Abstract
This paper explores the implications of blocking dualitypioneered by Fulkerson et al.in the context of p-modulus on networks. Fulkerson blocking duality is an analog on networks to the method of conjugate families of curves in the plane. The technique presented here leads to a general framework for studying families of objects on networks; each such family has a corresponding dual family whose p-modulus is essentially the reciprocal of the original family's. As an application, we give a modulus-based proof for the fact that effective resistance is a metric on graphs. This proof immediately generalizes to yield a family of graph metrics, depending on the parameter p, that continuously interpolates among the shortest-path metric, the effective resistance metric, and the min-cut ultrametric. In a second application, we establish a connection between Fulkerson blocking duality and the probabilistic interpretation of modulus. This connection, in turn, provides a straightforward proof of several monotonicity properties of modulus that generalize known monotonicity properties of effective resistance. Finally, we use this framework to expand on a result of Lovasz in the context of randomly weighted graphs.
Table of Contents
Description
Click on the DOI link to access the article (may not be free).
Publisher
Springer
Journal
Book Title
Series
Annali di Matematica Pura ed Applicata;v.198:no.3
Digital Collection
Finding Aid URL
Use and Reproduction
Archival Collection
PubMed ID
DOI
ISSN
0373-3114