Min-cost-flow preserving bijection between subgraphs and orientations

DOI10.37236/10940MaRDI QIDQ2111782zbMATHOpenAlexFDO

Authors Izhak Elmaleh, Ohad Noy Feldheim

Publication date 17 January 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.09250

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-edge-connecting orientations\(k\)-edge-connecting subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21) Connectivity (05C40)

Abstract: Consider an undirected graph $G=(V,E)$. A subgraph of $G$ is a subset of its edges, whilst an orientation of $G$ is an assignment of a direction to each edge. Provided with an integer circulation-demand $d:VomathbbZ$, we show an explicit and efficiently computable bijection between subgraphs of $G$ on which a $d$-flow exists and orientations on which a $d$-flow exists. Moreover, given a cost function $w:Eo(0,infty)$ we can find such a bijection which preserves the $w$-min-cost-flow. In 2013, Kozma and Moran showed, using dimensional methods, that the number of subgraphs $k$-connecting a vertex $s$ to a vertex $t$ is the same as the number of orientations $k$-connecting $s$ to $t$. An application of our result is an efficient, bijective proof of this fact.

Recommendations

• Geometric bijections between spanning subgraphs and orientations of a graph
• scientific article; zbMATH DE number 1146228
• scientific article; zbMATH DE number 2248469
• Optimal orientations of subgraphs of complete bipartite graphs
• Eulerian Orientations and Circulations

Cites work

• scientific article; zbMATH DE number 6382860 (Why is no real title available?)
• scientific article; zbMATH DE number 2053394 (Why is no real title available?)
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A note on two problems in connexion with graphs
• A quick method for finding shortest pairs of disjoint paths
• Distances in orientations of graphs
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• Shattering, graph orientations, and connectivity
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings

This page was built for publication: Min-cost-flow preserving bijection between subgraphs and orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111782)