Name
Title | ||
|---|---|---|
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams |
Abstract | ||
|---|---|---|
We initiate the study of $k$-edge-connected orientations of undirected graphs through edge flips for $k \geq 2$. We prove that in every orientation of an undirected $2k$-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is $k$-edge-connected. This yields an ``edge-flip 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-flip 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$. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/1.9781611977073.56 | ACM-SIAM Symposium on Discrete Algorithms (SODA) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Yuni Iwamasa | 2 | 0 | 1.01 |
| Naonori Kakimura | 3 | 59 | 21.18 |
| Naoyuki Kamiyama | 4 | 80 | 23.40 |
| Yusuke Kobayashi | 5 | 106 | 21.98 |
| Shun-ichi Maezawa | 6 | 0 | 0.34 |
| Yuta Nozaki | 7 | 0 | 0.68 |
| Yoshio Okamoto | 8 | 170 | 28.50 |
| Kenta Ozeki | 9 | 0 | 0.68 |