| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2018-12-12 10:25 Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou (Tohoku Univ.)  COMP2018-32 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | {sc Coloring reconfiguration} is one of the most well-studied reconfiguration problems. In the problem, we are given two proper (vertex-)colorings of a graph using at most $k$ colors, and asked to determine whether there exists a transform between them by recoloring only a single vertex at a time, while maintaining a proper coloring. It is known that this problem is solvable in polynomial time if $kleq3$, while is PSPACE-complete for a fixed $kgeq4$. In this paper, we study this problem from a viewpoint of recolorability constraints, which is given in terms of a graph $R$ whose vertices are colors, and each edge represents a pair of colors that can be recolored directly. In this paper, we show that this generalized problem can be solved in linear time if $R$ is of maximum degree at most two. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | combinatorial reconfiguration / graph algorithm / graph coloring / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 118, no. 356, COMP2018-32, pp. 7-14, Dec. 2018. | |
| Paper # | COMP2018-32 | |
| Date of Issue | 2018-12-05 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2018-32 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2018-12-12 - 2018-12-12 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tohoku University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2018-12-COMP |
| Language | English |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem |
| Sub Title (in English) | |
| Keyword(1) | combinatorial reconfiguration |
| Keyword(2) | graph algorithm |
| Keyword(3) | graph coloring |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Hiroki Osawa |
| 1st Author's Affiliation | Tohoku University (Tohoku Univ.) |
| 2nd Author's Name | Akira Suzuki |
| 2nd Author's Affiliation | Tohoku University (Tohoku Univ.) |
| 3rd Author's Name | Takehiro Ito |
| 3rd Author's Affiliation | Tohoku University (Tohoku Univ.) |
| 4th Author's Name | Xiao Zhou |
| 4th Author's Affiliation | Tohoku University (Tohoku Univ.) |
| Speaker | Author-1 |
| Date Time | 2018-12-12 10:25:00 |
| Presentation Time | 25 minutes |
| Registration for | COMP |
| Paper # | COMP2018-32 |
| Volume (vol) | vol.118 |
| Number (no) | no.356 |
| Page | pp.7-14 |
| #Pages | 8 |
| Date of Issue | 2018-12-05 (COMP) |
[Return to Top Page]