文献

J-GLOBAL ID：201602235933204005   整理番号：16A1323978

線形計画問題によるVizing予想へのアプローチ

著者 (1件)： 古谷倫貴 (北里大)
資料名： オペレーションズ・リサーチ
巻： 61  号： 12  ページ： 858-864  発行年： 2016年12月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： Vizing予想(任意の二つのグラフG,Hのデカルト積G.+.Hの支配数は,Gの支配数とHの支配数の積以上となる)は,グラフの支配数に関する最も有名な未解決予想である。この命題は,支配数を実数上に拡張した断片的支配数に置き換えたものについては成り立つことが比較的簡単に示されるが,その容易さは問題を線形計画問題に帰着できることに由来する。本稿ではその証明を通して,グラフ理論と最適化問題の関係を再確認したい。(著者抄録)

シソーラス用語： 線形計画法 ,  *予測 ,  *集合 ,  グラフ ,  *グラフ理論 ,  最適化問題
準シソーラス用語： *Vizing予想 ,  *支配集合

分類 (1件)： ネットワーク法  (KA03040X)

引用文献 (9件)：

• T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, 1998.
• T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination inn Graphs: Advanced Topics, Marcel Dekker, 1998.
• W. Imrich and S. Klavžar, Product graphs. Structure and recognition, Wiley-Interscience, 2000.
• O. Ore, Theory of Graphs, Vol. 38, American Mathematical Society Colloquium Publications, 1962.
• V. G. Vizing, “Some unsolved problems in graph theory,“ Uspekhi Matematicheskikh Nauk, 23, pp. 117-134, 1968.

タイトルに関連する用語 (3件)： 線形計画 ,  問題 ,  予想