文献

J-GLOBAL ID：201002241339466114   整理番号：10A0930560

Konig-Egervaryグラフおよび非Edmonds

Koenig-Egervary Graphs are Non-Edmonds

著者 (1件)： MARK KAYLL P. (Univ. Montana, MT, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 26  号： 5  ページ： 721-726  発行年： 2010年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Konig-Egervaryグラフは,その最大マッチングが頂点によるその最小位数被覆に対して等濃度であるグラフである。Edmonds(J Res Nat Bur Standard Sect B 69B:125~130,1965)は,グラフG=(V,E)の完全マッチングポリトープを,制約の2つのファミリである”頂点飽和”および”blossom”を満足する非負ベクトルx∈R^Eの集合として特性化した。後者の制約が前者に含まれるグラフを非-Edmondsと称した。本論文は,その表題の主張である,1つは組合せの,1つはアルゴリズムの2つの証明について述べた。どちらの証明も,de Carvalho等(J Combin Theory SerB 92:319~324,2004)により非-Edmondsグラフの特性に依拠しなかった。(翻訳著者抄録)

シソーラス用語： グラフ ,  *グラフ理論 ,  マッチング ,  頂点 ,  被覆 ,  濃度 ,  飽和 ,  ベクトル ,  集合 ,  制約条件 ,  組合せ問題 ,  アルゴリズム ,  キャラクタリゼーション
準シソーラス用語： *Konig-Egervaryグラフ ,  *ポリトープ ,  位数 ,  特性化

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

引用文献 (12件)：

• Birkhoff, G.: Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Revista A 5, 147-151(1946)
• Bondy, J. A., Murty, U. S. R.: Graph Theory. Springer, New York (2008)
• de Carvalho, M. H., Lucchesi, C. L., Murty, U. S. R.: The perfect matching polytope and solid bricks. J. Combin. Theory Ser. B 92, 319-324(2004)
• Chvátal, V.: Linear Programming. W. H. Freeman and Co., New York (1983)
• Deming, R. W.: Independence numbers of graphs-an extension of the Koenig-Egervary theorem. Discrete Math.27, 23-33(1979)

タイトルに関連する用語 (1件)： グラフ