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

eigenvaluesmatrix multiplicationregularity

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) Approximation algorithms (68W25) Analysis of algorithms (68W40)

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)

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

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)