Laplacians for flow networks

Joshua A. Taylor; Franz S. Hover

doi:10.1137/100787726

Laplacians for flow networks

Joshua A. Taylor, Franz S. Hover

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We define a class of Laplacians for multicommodity, undirected flow networks, and bound their smallest nonzero eigenvalues with a generalization of the sparsest cut.

Original language	English (US)
Pages (from-to)	1349-1364
Number of pages	16
Journal	SIAM Journal on Discrete Mathematics
Volume	25
Issue number	3
DOIs	https://doi.org/10.1137/100787726
State	Published - 2011
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Cheeger inequality
Multicommodity flow network
Sparsest cut
Spectral graph theory

Access to Document

10.1137/100787726

Cite this

@article{fe630c5b992f4401a878cf355266f49c,

title = "Laplacians for flow networks",

abstract = "We define a class of Laplacians for multicommodity, undirected flow networks, and bound their smallest nonzero eigenvalues with a generalization of the sparsest cut.",

keywords = "Cheeger inequality, Multicommodity flow network, Sparsest cut, Spectral graph theory",

author = "Taylor, {Joshua A.} and Hover, {Franz S.}",

year = "2011",

doi = "10.1137/100787726",

language = "English (US)",

volume = "25",

pages = "1349--1364",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Laplacians for flow networks

AU - Taylor, Joshua A.

AU - Hover, Franz S.

PY - 2011

Y1 - 2011

N2 - We define a class of Laplacians for multicommodity, undirected flow networks, and bound their smallest nonzero eigenvalues with a generalization of the sparsest cut.

AB - We define a class of Laplacians for multicommodity, undirected flow networks, and bound their smallest nonzero eigenvalues with a generalization of the sparsest cut.

KW - Cheeger inequality

KW - Multicommodity flow network

KW - Sparsest cut

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=82955165675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=82955165675&partnerID=8YFLogxK

U2 - 10.1137/100787726

DO - 10.1137/100787726

M3 - Article

AN - SCOPUS:82955165675

SN - 0895-4801

VL - 25

SP - 1349

EP - 1364

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Laplacians for flow networks

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this