Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Nghiên cứu tính toán về phân hoạch đồ thị
Tóm tắt
Cho G = (N, E) là một đồ thị vô hướng có trọng số cạnh. Vấn đề phân hoạch đồ thị là việc phân chia tập hợp đỉnh N thành k tập con chập không giao nhau với kích thước xác định, nhằm tối thiểu hóa tổng trọng số của các cạnh nối các đỉnh trong các tập con khác nhau của phân hoạch. Chúng tôi trình bày một nghiên cứu số về việc sử dụng các kỹ thuật dựa trên trị riêng để tìm các giới hạn trên và giới hạn dưới cho vấn đề này. Kết quả cho việc phân đôi các đồ thị có tới hàng nghìn đỉnh được cung cấp, và đối với các đồ thị nhỏ, một số kết quả phân ba cũng được trình bày. Chúng tôi cho thấy rằng các kỹ thuật này rất ổn định và luôn mang lại các giới hạn trên và giới hạn dưới có khoảng cách tương đối thường là vài điểm phần trăm.
Từ khóa
#phân hoạch đồ thị #trọng số cạnh #kỹ thuật trị riêng #giới hạn trên #giới hạn dướiTài liệu tham khảo
N. Alon and V.D. Milman, “λ 1, isoperimetric inequalities for graphs and superconcentrators,”JCT 38 (1985) 73–88.
S. Areibi and A. Vannelli, Personal communication, technical report, University of Waterloo, Waterloo, Ontario, Canada, 1993.
S.T. Barnard and H.D. Simon, “A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems,” technical report RNR-092-033, NASA Ames Research Center, Moffett Field, CA 94035, November 1992 (to appear inConcurrency: Practice and Experience).
E.R. Barnes, “An algorithm for partitioning the nodes of a graph,”SIAM Journal on Algebraic and Discrete Mathematics 3 (1982) 541–550.
E.R. Barnes, A. Vannelli and J.Q. Walker, “A new heuristic for partitioning the nodes of a graph,”SIAM Journal on Discrete Mathematics 1 (1988) 299–305.
R.B. Boppana, “Eigenvalues and graph bisection: An average case analysis,” in:Proceedings of the 28th Annual Symposium on Computer Science (IEEE, London, 1987) pp. 280–285.
T.N. Bui and C. Jones, “A heuristic for reducing fill-in in sparse matrix factorization,” in:Proceedings of the 6th SIAM Conference on Parallel Processing, 1993.
T.N. Bui and B.R. Moon, “Hyperplane synthesis for genetic algorithms,” in:Proceedings of the 5th International Conference on Genetic Algorithms, 1993.
J. Cullum, W.E. Donath and P. Wolfe, “The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices,”Mathematical Programming Study 3 (1975) 35–55.
D.M. Cvetkovic, M. Doob and H. Sachs,Spectra of Graphs — Theory and Applications (Academic Press, New York, NY, 1979).
D. Deuermeyer, “Large-scale solutions in structural analysis,”CRAY Channels 12(1) (1990) 15–17.
W.E. Donath and A.J. Hoffman, “Lower bounds for the partitioning of graphs,”IBM Journal of Research and Development 17 (1973) 420–425.
S.W. Hadley, B.L. Mark and A. Vannelli, “An efficient eigenvector approach for finding netlist partitions,”IEEE Transactions on Computer-Aided Design 11 (1992) 885–892.
R. Horn and C. Johnson,Matrix Analysis (Cambridge University Press, New York, 1985).
D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, “Optimization by simulated annealing: an experimental evaluation; part 1, graph partitioning,”Operations Research 37 (1989) 865–892.
M. Juvan and B. Mohar, “Optimal linear labelings and eigenvalues of graphs,”Discrete Applied Mathematics 36 (1992) 153–168.
B.W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,”The Bell System Technical Journal 49 (1970) 291–307.
T. Lengauer,Combinatorial algorithms for integrated circuit layout (John Wiley and Sons, Chicester, 1990).
D.G. Luenberger,Linear and Nonlinear Programming, second edition (Addison-Wesley, Reading, Massachusetts, 1984).
M.R. Rao M. Conforti and A. Sassano, “The equipartition polytope i and ii,”Mathematical Programming 49 (1990) 49–90.
F. Rendl and H. Wolkowicz, A projection technique for partitioning the nodes of a graph. Technical Report CORR 90-20, University of Waterloo, Waterloo, Canada, 1990.
H. Schramm and J. Zowe, “A combination of the bundle approach and the trust region concept,” in: J. Guddat et al., editor,Advances in Mathematical Optimization (Akademie Verlag Berlin, 1988).
H. Schramm and J. Zowe, “A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,”SIAM Journal on Optimization 2 (1992) 121–152.
D.S. Scott, Block lanczos software for symmetric eigenvalue problems, technical report 84-08, Oak Ridge National laboratory, 1979.
H. Simon, Personal communication, technical report, NASA Ames Research Center, Moffett Field, CA, 1993.
H.D. Simon, “Partitioning of unstructured problems for parallel processing,”Computing Systems in Engineering 2(2/3) (1991) 135–148.
V. Venkatakrishnan, H. Simon and T. Barth, “A mimd implementation of a parallel Euler solver for unstructured grids,”The Journal of Supercomputing 6(2) (1992) 117–127.
H. Wolkowicz and G.P.H. Styan, “More bounds for eigenvalues using traces,”Linear Algebra and its Applications 31 (1980) 1–17.