@techreport{oai:ipsj.ixsq.nii.ac.jp:00241028,
 author = {佐藤, 景大 and 高岡, 旭},
 issue = {12},
 month = {Nov},
 note = {部分グラフ同型性判定問題とは，2 つのグラフ G と H が与えられたときに G が H と同型な部分グラフを含むかを判定する問題である．順序付き部分グラフ同型性判定問題は今村・大館・斎藤（2024）によって提案された問題であり，グラフそのものとともに頂点順序が与えられたときに順序を保ったまま頂点を割り当てる制限付きの部分グラフ同型性判定問題である．順序付き部分グラフ同型性判定問題に対しては入力のグラフが区間順序を持つ区間グラフであるときに多項式時間可解であることが知られている．一方，比較可能順序を持つ二部グラフ，完全消去順序を持つスプリットグラフ，補比較可能順序を持つ補二部グラフ上での順序付き部分グラフ同型性判定問題は NP 完全である．本論文では 2 方向直交半直線交差グラフ，adjusted interval digraphs，signed interval digraphs 上での順序付き部分グラフ同型性判定問題を解く多項式時間アルゴリズムを提案する．これらのグラフクラスは，区間グラフと共に，min ordering，または X-underbar property と呼ばれる共通の特徴づけを持つことが知られている．さらに，弦二部グラフと強弦グラフ上での順序付き部分グラフ同型性判定問題が NP 完全であることを示す．},
 title = {Min-orderableグラフの順序付き部分グラフ同型性判定問題},
 year = {2024}
}