Cuts, trees and \(\ell_1\)-embeddings of graphs (Q705742): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q60608702, #quickstatements; #temporary_batch_1710276387428 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q60608702 / rank | |||
Normal rank |
Revision as of 22:47, 12 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cuts, trees and \(\ell_1\)-embeddings of graphs |
scientific article |
Statements
Cuts, trees and \(\ell_1\)-embeddings of graphs (English)
0 references
14 February 2005
0 references
It is investigated when the metric obtained by associating non-negative weights to the edges of a graph can be embedded within constant distortion into an \(\ell_1\)-space. Such an embedding with no distortion, i.e., an isometric embedding, exists if and only if the graph has no \(K_{2,3}\) minor. The optimal distortion \(c_1(G)\) is equal to the worst possible gap attained by a multicommodity flow problem on \(G\). It is conjectured that \(c_1(G)\) is bounded for any nontrivial minor-closed family of graphs. If \(G\) is series-parallel (or even if it has treewidth 2), then \(c_1(G)<14\) and an embedding can be found in polynomial time. Further, \(c_1(G)=O(\log \chi(G))\) with \(\chi(G)\) the Euler-characteristic of \(G\). The embeddings are determined via distributions over cuts and trees, respectively. In the tree case, lower bounds are given, as well.
0 references
metric on graphs
0 references
isometric embedding
0 references
minor
0 references
multicommodity flow problem
0 references
tree
0 references