文献

J-GLOBAL ID：202002298838845795   整理番号：20A1027651

制限された2鎖部分グラフ被覆による単純三角形グラフの認識【JST・京大機械翻訳】

Recognizing simple-triangle graphs by restricted 2-chain subgraph cover

著者 (1件)： Takaoka Asahi (Department of Information Systems Creation, Kanagawa University, Rokkakubashi 3-27-1, Kanagawa-ku, Kanagawa, 221-8686, Japan)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 279  ページ： 154-167  発行年： 2020年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 単純三角形グラフ(PIグラフとしても知られている)は,水平線上の点と別の水平線上の間隔によって定義される三角形の族の交差グラフである。単純三角形グラフに対する認識問題は長年のオープン問題であり,最近多項式時間アルゴリズム(Mertzios,2015)が与えられている。本論文のアプローチとともに,単純三角形グラフのためのより簡単な認識アルゴリズムを示した。これを行うために,二部グラフGとGのエッジの集合Fを与え,二つの連鎖サブグラフの一つがFにエッジを持たないようなGの2鎖サブグラフカバーを見出した。ここでは,nとmがそれぞれGの頂点とエッジの数であり,mがGの2つの独立した集合間の非エッジの数である,この問題のためのO(n2min{m,m})時間アルゴリズムを示した。この結果を用いて,簡単な三角形グラフに対する認識問題を,O(n2min{m,m})時間において解くことができることを示した。ここで,mは与えられたグラフの非エッジ数である。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *被覆 ,  *部分グラフ
準シソーラス用語： 二部グラフ ,  認識アルゴリズム ,  多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (6件)： チェーンカバー ,  グラフサンドイッチ問題 ,  PIグラフ ,  認識アルゴリズム ,  単純三角形グラフ ,  しきい値次元2グラフ

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 制限 ,  部分グラフ ,  三角形 ,  グラフ