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)
coloringapproximation algorithmsrandomized algorithmsproperty testingclustering problemshereditary graph properties
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (10)
Testing metric properties ⋮ Property testing of the Boolean and binary rank ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ Approximate membership for regular languages modulo the edit distance ⋮ Testing Expansion in Bounded-Degree Graphs ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Testing hypergraph colorability ⋮ Sublinear-time Algorithms ⋮ Tolerant property testing and distance approximation ⋮ A large lower bound on the query complexity of a simple Boolean function
This page was built for publication: Abstract Combinatorial Programs and Efficient Property Testers
