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

DOI10.1007/s10852-011-9154-4zbMath1238.05216MaRDI QIDQ662140

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

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 complexity; graph partitioning; linear algebra; edge-centric representation

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

15A99: Basic linear algebra

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient simulated annealing on fractal energy landscapes
• Graph partitioning by eigenvectors
• Fourier and Taylor series on fitness landscapes
• A linear time algorithm for graph partition problems
• Finding good approximate vertex and edge partitions is NP-hard
• A new adaptive multi-start technique for combinatorial global optimizations
• Expected complexity of graph partitioning problems
• A note on approximating Max-Bisection on regular graphs
• Lock-gain based graph partitioning
• Recent directions in netlist partitioning: a survey
• On the Quality of Spectral Separators
• The intractability of computing the minimum distance of a code