A deterministic algorithm for the Frieze-Kannan regularity lemma

DOI10.1137/110846373MaRDI QIDQ2902884zbMATH OpenOpenAlexWikidataFDO

Authors Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, 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

eigenvaluesregularitymatrix multiplication

Mathematics Subject Classification ID

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

Recommendations

• A deterministic algorithm for the Frieze-Kannan regularity lemma
• On regularity lemmas and their algorithmic applications
• An optimal algorithm for finding Frieze-Kannan regular partitions
• A fast new algorithm for weak graph regularity
• scientific article; zbMATH DE number 1256685

Cited in

(10)

• Erratum to: ``On regularity lemmas and their algorithmic applications
• Graph summarization with quality guarantees
• Regularity lemmas and combinatorial algorithms
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• An optimal algorithm for finding Frieze-Kannan regular partitions
• scientific article; zbMATH DE number 2119673 (Why is no real title available?)
• Amplification and Derandomization without Slowdown
• A fast new algorithm for weak graph regularity
• On regularity lemmas and their algorithmic applications
• An algorithmic version of the blow-up lemma

This page was built for publication: A deterministic algorithm for the Frieze-Kannan regularity lemma

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