Abstract Combinatorial Programs and Efficient Property Testers
From MaRDI portal
Publication:5317165
DOI10.1137/S009753970444199XzbMath1075.68099MaRDI QIDQ5317165
Christian Sohler, Artur Czumaj
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
coloring; approximation algorithms; randomized algorithms; property testing; clustering problems; hereditary graph properties
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Testing Expansion in Bounded-Degree Graphs, Sublinear-time Algorithms, Approximate membership for regular languages modulo the edit distance, On the benefits of adaptivity in property testing of dense graphs, Small space representations for metric min-sum \(k\)-clustering and their applications, A large lower bound on the query complexity of a simple Boolean function, Testing hypergraph colorability, Testing metric properties, Tolerant property testing and distance approximation