Fast Approximate Graph Partitioning Algorithms

DOI10.1137/S0097539796308217zbMath0936.68109OpenAlexW1977360022MaRDI QIDQ4268865

No author found.

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796308217

zbMATH Keywords

graph partitioningapproximation algorithmsspreading metricsgraph separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15)

Related Items (15)

\(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS ⋮ An exact algorithm for min-max hyperstructure equipartition with a connected constraint ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ A general variable neighborhood search approach for the minimum load coloring problem ⋮ On treewidth, separators and Yao's garbling ⋮ Dynamic Balanced Graph Partitioning ⋮ On treewidth approximations. ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ The application of cluster analysis in geophysical data interpretation ⋮ Inoculation strategies for victims of viruses and the sum-of-squares partition problem ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Coloring Graphs with Minimal Edge Load ⋮ Balanced partitions of trees and applications

This page was built for publication: Fast Approximate Graph Partitioning Algorithms