Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Coloring Reconfiguration Problem on Specific Graph Classes Masalah Konfigurasi Semula Mewarna pada Kelas Graf Tertentu

Tatsuhiko HATANAKA, Takehiro ITO, Xiao ZHOU

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Kami mengkaji masalah mengubah satu (puncak) c-mewarna graf kepada graf lain dengan menukar hanya satu penetapan warna bucu pada satu masa, sambil pada setiap masa mengekalkan c-mewarna, di mana c menunjukkan bilangan warna. Masalah keputusan ini diketahui sebagai PSPACE-lengkap walaupun untuk graf dwipartit dan sebarang pemalar tetap c ≥ 4. Dalam kertas kerja ini, kami mengkaji masalah dari sudut pandangan kelas graf. Kami mula-mula menunjukkan bahawa masalah itu kekal PSPACE-lengkap untuk graf kord walaupun jika c ialah pemalar tetap. Kami kemudian menunjukkan bahawa, walaupun ketika c adalah sebahagian daripada input, masalahnya boleh diselesaikan dalam masa polinomial untuk beberapa kelas graf, seperti k-pokok dengan sebarang integer k ≥ 1, graf belah dan graf sempurna yang remeh.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E102-D No.3 pp.423-429
Tarikh penerbitan
2019/03/01
Diumumkan
2018/10/30
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2018FCP0005
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
kategori

Pengarang

Tatsuhiko HATANAKA
  Tohoku University
Takehiro ITO
  Tohoku University
Xiao ZHOU
  Tohoku University

Kata kunci

Contents [show]