TY - GEN
T1 - Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams
AU - Ito, Takehiro
AU - Iwamasa, Yuni
AU - Kakimura, Naonori
AU - Kamiyama, Naoyuki
AU - Kobayashi, Yusuke
AU - Maezawa, Shun Ichi
AU - Nozaki, Yuta
AU - Okamoto, Yoshio
AU - Ozeki, Kenta
N1 - Funding Information:
This work was supported by JSPS KAKENHI Grant Numbers JP20H05793, JP20H05795, JP20K11670, JP20K11692, JP19K11814, JP18H04091, JP18H05291, and JP21H03397, Japan.
Publisher Copyright:
Copyright © 2022 by SIAM Unauthorized reproduction of this article is prohibited.
PY - 2022
Y1 - 2022
N2 - We initiate the study of k-edge-connected orientations of undirected graphs through edge ips for k 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that ipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k-edge-connected. This yields an \edge-ip based"new proof of Nash-Williams' theorem: an undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected. As another consequence of the theorem, we prove that the edge-ip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k + 2)-edge-connected. This has been known to be true only when k = 1.
AB - We initiate the study of k-edge-connected orientations of undirected graphs through edge ips for k 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that ipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k-edge-connected. This yields an \edge-ip based"new proof of Nash-Williams' theorem: an undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected. As another consequence of the theorem, we prove that the edge-ip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k + 2)-edge-connected. This has been known to be true only when k = 1.
UR - http://www.scopus.com/inward/record.url?scp=85127851632&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85127851632&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85127851632
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1342
EP - 1355
BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PB - Association for Computing Machinery
T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Y2 - 9 January 2022 through 12 January 2022
ER -