有界経路幅グラフのリスト彩色再構成問題

HATANAKA Tatsuhiko; ITO Takehiro; ZHOU Xiao

文献

J-GLOBAL ID：201502275139416056 整理番号：15A0745179

有界経路幅グラフのリスト彩色再構成問題

The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=15A0745179&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=15A0745179&from=J-GLOBAL&jstjournalNo=U0466A") }}

著者 (3件)： , ,
資料名：
巻： E98.A 号： 6 ページ： 1168-1178 (J-STAGE) 発行年： 2015年
JST資料番号： U0466A ISSN： 1745-1337 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

本論文は,グラフの各一リスト(頂点)に許容される色のリストを与え,リスト彩色を常時維持するが,グラフのリスト彩色を,他のリスト彩色に一時に一頂点の彩色割当てだけを変化させて変換する問題を研究する。この問題は,二部平面グラフに対しPSPACE完全であることが知られている。本論文では,最初にこの問題は,二部平面グラフの真のサブクラスを形成する二部直並列グラフに対してさえPSPACE完全に留まることを示す。この簡約化は,実際に経路幅2のグラフに対するPSPACE完全性を示し,閾値グラフに拡張できることに注目する。これと対比して,本論文は,経路幅1のグラフに対する問題を解く多項式時間アルゴリズムを与える。これにより本論文は,経路幅についてこの問題の鋭い解析を示す。(翻訳著者抄録)

, , , , , , , , , , , , ,
, , , , , ,

グラフ理論基礎

引用文献 (28件)：

[1] M. Bonamy, M. Johnson, I. Lignos, V. Patel, amd D. Paulusma, “Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs,” J. Combinatorial Optimization, vol.27, pp.132-143, 2014.
[2] M. Bonamy and N. Bousquet, “Recoloring bounded treewidth graphs,” Electronic Notes in Discrete Mathematics, vol.44, pp.257-262, 2013.
[3] P. Bonsma, “Rerouting shortest paths in planar graphs,” Proc. FSTTCS 2012, LIPIcs 18, pp.337-349, 2012.
[4] P. Bonsma, “The complexity of rerouting shortest paths,” Theor. Comput. Sci., vol.510, pp.1-12, 2013.
[5] P. Bonsma and L. Cereceda, “Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances,” Theor. Comput. Sci., vol.410, pp.5215-5226, 2009.

, , , , ,

前のページに戻る