A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma

DOI10.1137/110846373zbMath1245.05127OpenAlexW1997230618WikidataQ124881250 ScholiaQ124881250MaRDI QIDQ2902884

Daniel M. Martin, Domingos jun. Dellamonica, Subrahmanyam Kalyanasundaram, Vojtěch Rödl, Asaf Shapira

Publication date: 22 August 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

regularityeigenvaluesmatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions, On Regularity Lemmas and their Algorithmic Applications, Amplification and Derandomization without Slowdown, Graph summarization with quality guarantees, Erratum: On Regularity Lemmas and their Algorithmic Applications, A fast new algorithm for weak graph regularity