Min-cost-flow preserving bijection between subgraphs and orientations

DOI10.37236/10940zbMATH Open1506.05081arXiv2112.09250OpenAlexW4316038097MaRDI QIDQ2111782FDOQ2111782

Authors: Izhak Elmaleh, Ohad Noy Feldheim 

Publication date: 17 January 2023

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

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.

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

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

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

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)

Cites Work

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

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)