Reconfiguration of list edge-colorings in a graph
11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | Article |
| 語言: | en_US |
| 出版: |
Springer Berlin / Heidelberg
2012
|
| 在線閱讀: | http://hdl.handle.net/1721.1/73858 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826210086838599680 |
|---|---|
| author | Ito, Takehiro Kaminski, Marcin Demaine, Erik D. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ito, Takehiro Kaminski, Marcin Demaine, Erik D. |
| author_sort | Ito, Takehiro |
| collection | MIT |
| description | 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings |
| first_indexed | 2024-09-23T14:42:23Z |
| format | Article |
| id | mit-1721.1/73858 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:42:23Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/738582022-10-01T22:06:42Z Reconfiguration of list edge-colorings in a graph Ito, Takehiro Kaminski, Marcin Demaine, Erik D. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing one edge color at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. First we show that this problem is PSPACE-complete, even for planar graphs of maximum degree 3 and just six colors. Then we consider the problem restricted to trees. We show that any list edge-coloring can be transformed into any other under the sufficient condition that the number of allowed colors for each edge is strictly larger than the degrees of both its endpoints. This sufficient condition is best possible in some sense. Our proof yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices using O(n [superscript 2]) recolor steps. This worst-case bound is tight: we give an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n [superscript 2]) recolor steps. 2012-10-10T18:03:39Z 2012-10-10T18:03:39Z 2009-07 2009-08 Article http://purl.org/eprint/type/JournalArticle 978-3-642-03366-7 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73858 Ito, Takehiro, Marcin Kamiński, and Erik D. Demaine. “Reconfiguration of List Edge-Colorings in a Graph.” Algorithms and Data Structures. Ed. Frank Dehne et al. LNCS Vol. 5664. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 375–386. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-03367-4_33 Algorithms and Data Structures Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg Other University Web Domain |
| spellingShingle | Ito, Takehiro Kaminski, Marcin Demaine, Erik D. Reconfiguration of list edge-colorings in a graph |
| title | Reconfiguration of list edge-colorings in a graph |
| title_full | Reconfiguration of list edge-colorings in a graph |
| title_fullStr | Reconfiguration of list edge-colorings in a graph |
| title_full_unstemmed | Reconfiguration of list edge-colorings in a graph |
| title_short | Reconfiguration of list edge-colorings in a graph |
| title_sort | reconfiguration of list edge colorings in a graph |
| url | http://hdl.handle.net/1721.1/73858 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT itotakehiro reconfigurationoflistedgecoloringsinagraph AT kaminskimarcin reconfigurationoflistedgecoloringsinagraph AT demaineerikd reconfigurationoflistedgecoloringsinagraph |