NDLI: Distribution-Free Connectivity Testing for Sparse Graphs

Content Provider	Springer Nature Link
Author	Halevy, Shirley Kushilevitz, Eyal
Copyright Year	2007
Abstract	We consider distribution-free property-testing of graph connectivity. In this setting of property testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain, and the testing algorithm has an oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, and testers were shown for very few properties. However, no distribution-free property testing algorithm was known for any graph property. We present the first distribution-free testing algorithms for one of the central properties in this area—graph connectivity (specifically, the problem is mainly interesting in the case of sparse graphs). We introduce three testing models for sparse graphs: • A model for bounded-degree graphs, • A model for graphs with a bound on the total number of edges (both models were already considered in the context of uniform distribution testing), and • A model which is a combination of the two previous testing models; i.e., bounded-degree graphs with a bound on the total number of edges. We prove that connectivity can be tested in each of these testing models, in a distribution-free manner, using a number of queries that is independent of the size of the graph. This is done by providing a new analysis to previously known connectivity testers (from “standard”, uniform distribution property-testing) and by introducing some new testers.
Starting Page	24
Ending Page	48
Page Count	25
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	51
Issue Number	1
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-10-09
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Property testing Distribution-free testing Connectivity testing Properties of sparse graphs Data Structures, Cryptology and Information Theory Computer Systems Organization and Communication Networks Algorithms Mathematics of Computing Theory of Computation Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Property Testing on k-Vertex-Connectivity of Graphs

Property Testing in Bounded Degree Graphs

Efficiently Testing Sparse GF(2) Polynomials

Testing Outerplanarity of Bounded Degree Graphs

Testing Periodicity

Regular Augmentation of Planar Graphs

On the Benefits of Adaptivity in Property Testing of Dense Graphs

Quantum Property Testing of Group Solvability

Property-Preserving Data Reconstruction

Distribution-Free Connectivity Testing for Sparse Graphs

Similar Documents

Property Testing on k-Vertex-Connectivity of Graphs

Property Testing in Bounded Degree Graphs

Efficiently Testing Sparse GF(2) Polynomials

Testing Outerplanarity of Bounded Degree Graphs

Testing Periodicity

Regular Augmentation of Planar Graphs

On the Benefits of Adaptivity in Property Testing of Dense Graphs

Quantum Property Testing of Group Solvability

Property-Preserving Data Reconstruction

Distribution-Free Connectivity Testing for Sparse Graphs