A note on edge-based graph partitioning and its linear algebraic structure

DOI10.1007/S10852-011-9154-4MaRDI QIDQ662140zbMATH OpenOpenAlexFDO

Authors Yourim Yoon, Yong-Hyuk Kim, Byung-Ro Moon

Publication date 21 February 2012

Published in JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10852-011-9154-4

zbMATH Keywords

computational complexityedge-centric representationgraph partitioninglinear algebra

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Basic linear algebra (15A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algorithms for graph partitioning problems by means of eigenspace relaxations
• scientific article; zbMATH DE number 736319
• A linear time algorithm for graph partition problems
• scientific article; zbMATH DE number 1418276
• A computational study of graph partitioning

Cites work

• A linear time algorithm for graph partition problems
• A new adaptive multi-start technique for combinatorial global optimizations
• A note on approximating Max-Bisection on regular graphs
• Efficient simulated annealing on fractal energy landscapes
• Expected complexity of graph partitioning problems
• Finding good approximate vertex and edge partitions is NP-hard
• Fourier and Taylor series on fitness landscapes
• Graph partitioning by eigenvectors
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 5117494 (Why is no real title available?)
• scientific article; zbMATH DE number 3763833 (Why is no real title available?)
• scientific article; zbMATH DE number 51371 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Lock-gain based graph partitioning
• On the Quality of Spectral Separators
• Recent directions in netlist partitioning: a survey
• The intractability of computing the minimum distance of a code

Cited in

(1)

• A mathematical design of genetic operators on \(\mathrm{GL}_n(\mathbb Z_2)\)

This page was built for publication: A note on edge-based graph partitioning and its linear algebraic structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662140)