頂点被覆
(Vertex cover から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 03:31 UTC 版)
グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には固定パラメータ容易性 (fixed-parameter tractability) があり、パラメータ化計算量理論の中心問題の1つである。
- ^ Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
- ^ Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. pp. pp.122-123. ISBN 3-540-65367-8
- ^ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47–63
- ^ Garey, M. R.; D. S. Johnson (1977). “The rectilinear Steiner tree problem is NP-complete”. SIAM Journal on Applied Mathematics 32 (4): 826–834. doi:10.1137/0132071.
- ^ a b Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3
- ^ Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover, p. 432, mentions both Gavril and Yannakakis. Garey, Michael R.; Johnson, David S. (1979 [2003]), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, p. 134, cites Gavril.
- ^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
- ^ I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").
- ^ Khot, S.; Regev, O. (2008), “Vertex cover might be hard to approximate to within 2-ε”, J. Comput. Syst. Sci. 74 (3): 335–349, doi:10.1016/j.jcss.2007.06.019.
[続きの解説]
「Vertex cover」の例文・使い方・用例・文例
- ふたをする → uncover ふたを取る.
Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
- Vertex coverのページへのリンク
