文献

J-GLOBAL ID：201802264949837802   整理番号：18A0328342

経路分割とk-経路頂点被覆との間の関係について【Powered by NICT】

On a relation between k -path partition and k -path vertex cover

著者 (2件)： Brause Christoph (Institute of Discrete Mathematics and Algebra, Faculty of Mathematics and Computer Science, TU Bergakademie Freiberg, 09596 Freiberg, Germany) ,  Krivos-Bellus Rastislav (Institute of Computer Science, Faculty of Science, Pavol Jozef Safarik University in Kosice, Jesenna 5, 040 01 Kosice, Slovakia)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 223  ページ： 28-38  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最小頂点被覆問題と最小頂点分割問題は,グラフ理論における中心的問題であり,多くの一般化が知られている。二例は最小のk-経路頂点被覆問題(M K PVCP)の次数kのどの経路をカバーする頂点最小集合を求めると,最小のk-経路分割問題(M K PPP),最大経路充填における経路の最小集合を求めるには,そのすべての経路が,高々k頂点を持つ。本論文では,M K PPPとM K PVCPの間の関係を提示した。それに基づいて,著者らはその不変量のための新しい限界と禁止部分グラフの観点からM K PVCPのNP困難性のための新しい十分条件を得る助けとなるであろう。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 部分グラフ ,  十分条件 ,  NP困難 ,  不変量 ,  *グラフ理論
準シソーラス用語： 禁止 ,  次数 ,  *頂点被覆 , 【Automatic Indexing@JST】

著者キーワード (3件)： 経路分割 ,  経路頂点被覆 ,  禁止部分グラフ

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

タイトルに関連する用語 (2件)： 経路 ,  頂点被覆