Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
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
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)