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

vertex covermaximum matchinghereditary propertiesconstant-time algorithmsminor-freeness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) 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)

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

• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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 Minimum Spanning Tree Weight in Sublinear Time
• Approximating the distance to properties in bounded-degree and general sparse graphs
• 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
• 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
• \(L^{2}\)-spectral invariants and convergent sequences of finite graphs

Cited in

(13)

• Sublinear Random Access Generators for Preferential Attachment Graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Algorithms on Subtree Filament Graphs
• Sublinear randomized algorithms for skeleton decompositions
• An improved constant-time approximation algorithm for maximum~matchings
• Sublinear time algorithms
• 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
• Linear time approximation algorithms for~degree~constrained subgraph problems
• Sublinear-time algorithms for approximating graph parameters
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• Algorithms on subgraph overlap graphs

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)