Loading...
Please wait, while we are loading the content...
Similar Documents
A fast new algorithm for weak graph regularity
| Content Provider | Scilit |
|---|---|
| Author | Fox, Jacob Lovász, László Miklós Zhao, Yufei |
| Copyright Year | 2019 |
| Description | We provide a deterministic algorithm that finds, in $ɛ^{-O(1)}n^{2}$ time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of $ɛ^{-O(1)}$ many complete bipartite graphs.As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most $ɛn^{v(H)}$, in time ɛ^{-O_{H}$(1)}n^{2}$. |
| Related Links | http://arxiv.org/pdf/1801.05037 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/E17D06308910088718F987EB1C8A6560/S0963548319000075a.pdf/div-class-title-a-fast-new-algorithm-for-weak-graph-regularity-div.pdf |
| Ending Page | 790 |
| Page Count | 14 |
| Starting Page | 777 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548319000075 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 5 |
| Volume Number | 28 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2019-09-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Hardware and Architecture Applied Mathematics Primary 05c85 Secondary 05c50 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
