| Item type |
SIG Technical Reports(1) |
| 公開日 |
2022-03-07 |
| タイトル |
|
|
タイトル |
最大次数3のグラフにおける辞書式深さ優先探索から極大辞書式最小パスへのサイズ保存対数領域帰着 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A Size-Preserving Logspace Reduction from Lexicographic Depth-First Search to Lexicographic Min-Max Path in Graphs of Maximum Degree Three |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
名古屋工業大学 |
| 著者所属 |
|
|
|
名古屋工業大学 |
| 著者所属 |
|
|
|
名古屋大学 |
| 著者所属 |
|
|
|
大阪大学 |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Osaka University |
| 著者名 |
細川, 秀樹
江口, 僚太
大舘, 陽太
泉, 泰介
|
| 著者名(英) |
Hideki, Hosokawa
Ryota, Eguchi
Yota, Otachi
Taisuke, Izumi
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
辞書順式深さ優先探索 (Lexicographic Depth-First Search: Lex-DFS) 問題とは，深さ優先探索問題において，隣接リストに存在する最初の未訪問の頂点へフォワードする制約を課した深さ優先探索である．また極大辞書式最小パス (Lexicographically minimal maximal path: LMMP) とは，Lex-DFS において最初のバックトラックが発生するまでのパスを発見する問題である．本論文では，最大次数 3 の無向グラフにおける Lex-DFS から LMMP への対数領域サイズ保存帰着を示す．本帰着と既知の結果を組み合わせることで，疎なグラフに対する劣線形領域 Lex-DFS アルゴリズムを実現するためには最大次数 3 の無向グラフに対する劣線形領域の LMMP アルゴリズムを実現すれば十分であることが結論づけられる． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Lexicographic DFS (Lex-DFS) is a popular variant of DFS, which requires the search head always moves to the first undiscovered neighbor in the adjacency list of the current vertex (as long as it exists). The lexicographic min-max path problem (LMMP) is a weaker variant of Lex-DFS, which requires us to output the prefix of Lex-DFS ordering up to the vertex where the first backtrack occurs. In this paper, we presents a size-preserving logspace reduction from Lex-DFS to LMMP for undirected graphs of maximum degree three. Combining this result with some prior work, one can conclude that it suffices to develop a sublinear-space LMMP algorithm for obtaining a sublinear-space Lex-DFS for sparse graphs. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2022-AL-187,
号 4,
p. 1-8,
発行日 2022-03-07
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL22187004.pdf (1.1 MB)
