文献

J-GLOBAL ID：201702232153025641   整理番号：17A1185901

禁止有向小行列式とKelly幅【Powered by NICT】

Forbidden directed minors and Kelly-width

著者 (2件)： Kintali Shiva (Department of Computer Science, Princeton University, Princeton, NJ 08540, United States) ,  Zhang Qiuyi (Mathematics Department, Princeton University, Princeton, NJ 08540, United States)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 662  ページ： 40-47  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 部分K DAGは部分k木の一般化である。部分k木が有界木幅をもつ無向グラフであるが,部分的K DAGが有界Kelly幅を持つ有向グラフである。無向グラフが,マイナーな3Kを持たない場合にのみ部分的1-木であることが知られている。本論文では,部分1DAGは三禁制有向小行列式,3K,4と5によって特徴づけられることを証明した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 無向グラフ ,  *行列式 ,  グラフ ,  有向グラフ
準シソーラス用語： 木幅 ,  有界 , 【Automatic Indexing@JST】

著者キーワード (5件)： 禁止マイナー ,  グラフ小行列式 ,  Kelly width ,  部分K DAG ,  木幅

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

タイトルに関連する用語 (1件)： 禁止