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

DOI10.1007/s10852-011-9154-4zbMath1238.05216OpenAlexW2011697549MaRDI 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 complexitygraph partitioninglinear algebraedge-centric representation

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Basic linear algebra (15A99)

Related Items (1)

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

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