文献

J-GLOBAL ID：201902262449743243   整理番号：19A1541711

エッジ2色グラフ上の頂点スイッチングの複雑性【JST・京大機械翻訳】

Complexity of Vertex Switching on Edge-Bicolored Graphs

著者 (2件)： Pang Ho Lam (Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China) ,  Cai Leizhen (Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11485  ページ： 339-351  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： エッジ双極化グラフは,各エッジが青色または赤色のいずれかで着色されている非有向グラフである。エッジ双極グラフの頂点でのスイッチング動作について考察した。頂点が青から赤に入射するすべてのエッジの頂点変化色でのスイッチングとその逆である。著者らは,頂点スイッチングを用いることの複雑さを研究し,青色グラフだけまたは青色と赤色グラフのために与えられた特性を満たすグラフにエッジ双極グラフを変換し,結合グラフ,Eulerグラフ,および非巡回グラフのようないくつかの基本的性質に対する多項式時間アルゴリズムとNP完全性証明を得た。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *スイッチング ,  *グラフ ,  有向グラフ
準シソーラス用語： NP完全性 ,  多項式時間アルゴリズム ,  巡回 ,  *複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： グラフアルゴリズム ,  エッジ二色グラフ ,  頂点スイッチング

分類 (2件)： パターン認識  (JE07000S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： エッジ ,  2色 ,  グラフ ,  頂点 ,  スイッチング ,  複雑性