文献

J-GLOBAL ID：202102273348949741   整理番号：21A3383038

(k,l)グラフにおけるエッジクリーク分割【JST・京大機械翻訳】

Edge clique partition in (k,l)-graphs

著者 (3件)： Jones Atila A. (Instituto Federal de Educacao, Ciencia e Tecnologia do Sudeste de Minas Gerais, Brazil) ,  Protti Fabio (Instituto de Computacao, Universidade Federal Fluminense, Brazil) ,  Del-Vecchio Renata R. (Instituto de Matematica, Universidade Federal Fluminense, Brazil)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 306  ページ： 89-97  発行年： 2022年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Gのエッジクリーク分割は,Gのあらゆるエッジを含むGのエッジ-ディスジョイントクリークの集合である。本研究では,cp(G)によって表示されたGのエッジクリーク分割の最小サイズを決定する計算の複雑さを調べた。この問題は分割グラフとK4フリーグラフに対してNP困難である。(k,l)グラフの階層構造,k独立集合とl完全集合に分割できるグラフに関するこの問題の完全な複雑性分類を確立した。さらに,多項式時間において,(k,l)グラフの興味深いサブクラスに対するcp(G)の値,すなわち分割差グラフ,部分2ツリー,および三角形格子を決定した。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *計算量 ,  階層構造 ,  NP困難 ,  三角格子
準シソーラス用語： 複雑性 ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (3件)： エッジクリーク分割 ,  NP完全 ,  (kl)グラフ

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

タイトルに関連する用語 (3件)： グラフ ,  エッジ ,  クリーク