Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams

Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun Ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun Ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Publisher	Association for Computing Machinery
Pages	1342-1355
Number of pages	14
ISBN (Electronic)	9781611977073
Publication status	Published - 2022
Event	33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States Duration: 2022 Jan 9 → 2022 Jan 12

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	2022-January

Conference

Conference	33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/Territory	United States
City	Alexander
Period	22/1/9 → 22/1/12

ASJC Scopus subject areas

Software
General Mathematics

Cite this

Ito, T., Iwamasa, Y., Kakimura, N., Kamiyama, N., Kobayashi, Y., Maezawa, S. I., Nozaki, Y., Okamoto, Y., & Ozeki, K. (2022). Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams. In ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 (pp. 1342-1355). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2022-January). Association for Computing Machinery.

Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams. / Ito, Takehiro; Iwamasa, Yuni; Kakimura, Naonori et al.
ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Association for Computing Machinery, 2022. p. 1342-1355 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2022-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ito, T, Iwamasa, Y, Kakimura, N, Kamiyama, N, Kobayashi, Y, Maezawa, SI, Nozaki, Y, Okamoto, Y & Ozeki, K 2022, Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams. in ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2022-January, Association for Computing Machinery, pp. 1342-1355, 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Alexander, United States, 22/1/9.

@inproceedings{c6100f15a6274257a65fc6eb7f28fc71,

title = "Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams",

abstract = "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.",

author = "Takehiro Ito and Yuni Iwamasa and Naonori Kakimura and Naoyuki Kamiyama and Yusuke Kobayashi and Maezawa, {Shun Ichi} and Yuta Nozaki and Yoshio Okamoto and Kenta Ozeki",

note = "Publisher Copyright: Copyright {\textcopyright} 2022 by SIAM Unauthorized reproduction of this article is prohibited.; 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 ; Conference date: 09-01-2022 Through 12-01-2022",

year = "2022",

language = "English",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1342--1355",

booktitle = "ACM-SIAM Symposium on Discrete Algorithms, SODA 2022",

}

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

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 -

Monotone edge ips to an orientation of maximum edge-connectivity a la Nash-Williams

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this