Sublinear graph approximation algorithms

DOI10.1007/978-3-642-16367-8_9MaRDI QIDQ4933367zbMATH OpenOpenAlexFDO

Authors Krzysztof Onak

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16367-8_9

zbMATH Keywords

constant-time algorithmshereditary propertiesmaximum matchingminor-freenessvertex cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• An improved constant-time approximation algorithm for maximum~matchings
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Distance Approximation in Bounded-Degree and General Sparse Graphs

Cites work

• \(L^{2}\)-spectral invariants and convergent sequences of finite graphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Separator Theorem for Planar Graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An improved constant-time approximation algorithm for maximum~matchings
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Approximation algorithms for combinatorial problems
• Graph minors. XX: Wagner's conjecture
• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Local Graph Partitions for Approximation and Testing
• On constant time approximation of parameters of bounded degree graphs
• On the ratio of optimal integral and fractional covers
• Property testing in bounded degree graphs
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• The price of being near-sighted

Cited in

(13)

• Sublinear-time algorithms for approximating graph parameters
• Sublinear randomized algorithms for skeleton decompositions
• Algorithms on subgraph overlap graphs
• Linear time approximation algorithms for~degree~constrained subgraph problems
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Sublinear time algorithms
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Algorithms on Subtree Filament Graphs
• Sublinear Random Access Generators for Preferential Attachment Graphs
• An improved constant-time approximation algorithm for maximum~matchings
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size

This page was built for publication: Sublinear graph approximation algorithms

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