文献

J-GLOBAL ID：201802260426568800   整理番号：18A1388633

より速い部分グラフの発見【JST・京大機械翻訳】

Finding even subgraphs even faster

著者 (6件)： Goyal Prachi (Indian Institute of Science, Bangalore, India) ,  Misra Pranabendu (The Institute of Mathematical Sciences, HBNI, Chennai, India) ,  Panolan Fahad (The Institute of Mathematical Sciences, HBNI, Chennai, India) ,  Philip Geevarghese (Chennai Mathematical Institute, India and UMI ReLaX) ,  Saurabh Saket (The Institute of Mathematical Sciences, HBNI, Chennai, India) ,  Saurabh Saket (Department of Informatics, University of Bergen, Norway)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 97  ページ： 1-13  発行年： 2018年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 方向性のないEulerエッジ分割問題において,著者らは無有向グラフと整数kを与え,その目的は,得られたグラフが全ての頂点が偶数度を持つ連結グラフであるようなkエッジを削除することである。得られたグラフが強く接続されるべき有向グラフにおける対応する問題とあらゆる頂点は,その外の程度が方向性Eulerエッジ変位と呼ばれるので,同じ程度を持つべきである。本論文では,コグラフマトロイドの代表的なファミリーを計算する技術を用いて,時間2O(k)nO(1)におけるこれらの問題を解決するアルゴリズムを設計し,Cyganらによるアルゴリズムを改善した。これらの問題をもたらす重要な洞察は,共グラフィックマトロイドの独立集合としての解を見ることである。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 指向性 ,  偶数 ,  *部分グラフ ,  アルゴリズム ,  有向グラフ ,  マトロイド
準シソーラス用語： 連結グラフ , 【Automatic Indexing@JST】

著者キーワード (5件)： Eulerエッジ削除 ,  FPTアルゴリズム ,  代表的な家族 ,  コグラフィックマトロイド ,  動的計画法

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 部分グラフ ,  発見