2026-05-20T04:10:12Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00234053 2025-01-19T09:53:35Z 1164:2592:11452:11598

有向非巡回グラフ上の長さ限定有向パスによる最小分割問題の困難性 Directed Path Partition Problem on Directed Acyclic Graphs 江藤, 宏 川原田, 隼介 Guohui, Lin 宮野, 英次 Tugce, Ozdemir 有向グラフ G=(V, E) とし，長さが k 以下の点素なパスによるグラフ分割問題について研究を行う．最小分割問題 (k-PP) とは，入力として有向グラフ G=(V, E) と整数 k が与えられてたとき，長さ k 以下のパスによるグラフ G を分割するパスの最小本数を出力することを目的とする．パスの長さkに着目したとき，k= technical report 情報処理学会 2024-05-01 application/pdf 研究報告アルゴリズム（AL） 14 2024-AL-198 1 5 2188-8566 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/234053/files/IPSJ-AL24198014.pdf jpn