Một phương trình lập trình tuyến tính cho vấn đề tìm kiếm đặc trưng con đồ thị nhiều phần tối đa

Springer Science and Business Media LLC - Tập 105 - Trang 329-344 - 2005
Denis Cornaz1
1Équipe Combinatoire et Optimisation, Case 189, UFR 921, Université Pierre et Marie Curie, Cedex Paris, France

Tóm tắt

Giả sử G là một đồ thị đơn, không hướng với tập đỉnh V(G) và tập cạnh E(G). Chúng ta gọi một tập con F là độc lập nếu F nằm trong tập cạnh của một đồ thị con nhiều phần hoàn toàn (không nhất thiết phải là đồ thị con gây ra) của G, ngược lại, F được gọi là phụ thuộc. Trong bài báo này, chúng tôi đặc trưng hóa các tập độc lập và các tập phụ thuộc tối thiểu của G. Chúng tôi lưu ý rằng mọi phụ thuộc tối thiểu của G đều có kích thước hai nếu và chỉ nếu G không chứa các cấu trúc quạt và lăng trụ. Chúng tôi đưa ra một phương trình lập trình tuyến tính 0-1 cho vấn đề sau: tìm trọng số tối đa của một đồ thị con nhiều phần hoàn toàn trong G, trong đó G có trọng số cạnh không âm. Phương trình này có thể có một số lượng ràng buộc theo cấp số mũ đối với |V(G)| nhưng chúng tôi chứng minh rằng phương trình liên tục của chương trình 0-1 này có thể được giải quyết trong thời gian đa thức.

Từ khóa


Tài liệu tham khảo

Cameron, K.: The maximum edge-weighted clique problem in complete multipartite graphs. J. Combin. Math. Combin. Comput. 9, 33–37 (1991) Cockayne, E.J., Hartnell, B.L.: Edge partitions of complete multipartite graphs into equal length circuits. J. Combinatorial Theory Ser. B 23 (2-3) 174–183 (1977) Cornaz, D., Fonlupt, J.: Chromatic characterization of biclique covers, to appear in Discrete Math. Fishburn, P.C., Hammer, P.L.: Bipartite dimensions and bipartite degrees of graphs. Discrete Math. 160, 127–148 (1996) Gregory, D.A., Vander, Meulen, K.N.: Sharp bounds for decompositions of graphs into complete r-partite subgraphs. J. Graph Theory 21 (4) 393–400 (1996) Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (2), 169–197 (1981) Ramirez-Alfonsín, J.L.: Cycle decompositions of complete and complete multipartite graphs. Australas. J. Combin. 11, 233–238 (1995) Monson S.D., Pullman N.J., Rees, R.: A survey of clique and biclique coverings and factorizations of (0,1)-matrices. Bulletin of the ICA 14, 17–86 (1995) Orlin, J.: Contentment in Graph Theory. Indag. Math. 39, 758–762 (1977) Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Applied Math. 131 (3), 651–654 (2003) Schrijver, A.: Combinatorial Optimization. Springer-Verlag, Berlin Heidelberg (2003)