NDLI: On testable properties in bounded degree graphs

Please wait, while we are loading the content...

Region-fault tolerant geometric spanners

A PTAS for TSP with neighborhoods among fat regions in the plane

Optimal dynamic vertical ray shooting in rectilinear planar subdivisions

Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition

A near linear time constant factor approximation for Euclidean bichromatic matching (cost)

Compacting cuts: a new linear formulation for minimum cut

Linear programming relaxations of maxcut

Near-optimal algorithms for maximum constraint satisfaction problems

Improved bounds for the symmetric rendezvous value on the line

Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization

Multiple source shortest paths in a genus g graph

Obnoxious centers in graphs

Maximum matching in graphs with an excluded minor

Faster dynamic matchings and vertex connectivity

Efficient algorithms for computing all low s-t edge connectivities and related problems

Analytic combinatorics: a calculus of discrete structures

Equilibria in online games

The approximation complexity of win-lose games

Convergence to approximate Nash equilibria in congestion games

Efficient contention resolution protocols for selfish agents

Strong price of anarchy

Better online buffer management

Considering suppressed packets improves buffer management in QoS switches

Instability of FIFO in the permanent sessions model at arbitrarily small network loads

On the separation and equivalence of paging strategies

Pull-based data broadcast with dependencies: be fair to users, not to items

Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry

Minimizing movement

Optimization problems in multiple-interval graphs

Approximation algorithms via contraction decomposition

A 1.875: approximation algorithm for the stable marriage problem

Improved algorithms for path, matching, and packing problems

Model-driven optimization using adaptive probes

Estimating the sortedness of a data stream

A near-optimal algorithm for computing the entropy of a stream

The communication and streaming complexity of computing the longest common and increasing subsequences

Efficient aggregation algorithms for probabilistic data

An unbiased pointing operator for unlabeled structures, with applications to counting and sampling

Approximating entropy from sublinear samples

Torpid mixing of local Markov chains on 3-colorings of the discrete torus

Probabilistic analysis of linear programming decoding

Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes

Deterministic pivoting algorithms for constrained ranking and clustering problems

Aggregation of partial rankings, p-ratings and top-m lists

Algorithms and incentives for robust ranking

Matroids, secretary problems, and online mechanisms

An algebraic algorithm for weighted linear matroid intersection

An elementary construction of constant-degree expanders

The k-orientability thresholds for Gn, p

The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation

On extremal subgraphs of random graphs

Online vertex colorings of random graphs without monochromatic subgraphs

On testable properties in bounded degree graphs

Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion

Approximation algorithms for embedding general metrics into trees

Embedding into $l^{2}∞$ is easy embedding into $l^{2}∞$ is NP-complete

Efficient subspace approximation algorithms

A divide and conquer algorithm for d-dimensional arrangement

Resilient search trees

Randomization does not help searching predecessors

Dynamic weighted ancestors

Ultra-succinct representation of ordered trees

Tree exploration with logarithmic memory

Testing for a theta

Deterministic rendezvous, treasure hunts and strongly universal exploration sequences

Planar graphs are in 1-STRING

On the bandwidth conjecture for 3-colourable graphs

Sandpile transience on the grid is polynomially bounded

Digraph measures: Kelly decompositions, games, and orderings

Approximating the spanning star forest problem and its applications to genomic sequence alignment

Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree

Whole genome duplications, multi-break rearrangements, and genome halving problem

Succinct indexes for strings, binary relations and multi-labeled trees

A simple storage scheme for strings achieving entropy bounds

A network formation game for bipartite exchange economies

Cheap labor can be expensive

Buying cheap is expensive: hardness of non-parametric multi-product pricing

Dynamic pricing for impatient bidders

Designing and learning optimal finite support auctions

On Bregman Voronoi diagrams

Zone diagrams: existence, uniqueness and algorithmic challenge

Approximate shortest paths in anisotropic regions

On bounded leg shortest paths problems

Counting colors in boxes

Energy efficient online deadline scheduling

Speed scaling for weighted flow time

Path-independent load balancing with unreliable machines

Layered multicast scheduling for the $L_{∞}$ objective

Lower bounds on average-case delay for video-on-demand broadcast protocols

Maximum s-t-flow with k crossings in $O(k^{3}n$ log n) time

Matrix scaling by network flow

Single source multiroute flows and cuts on uniform capacity networks

Island hopping and path colouring with applications to WDM network design

Maximum independent sets in graphs of low degree

Noisy binary search and its applications

Multiple choice tries and distributed hash tables

Making deterministic signatures quickly

A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths

On the K-simple shortest paths problem in weighted directed graphs

Semi-oblivious routing: lower bounds

Optimal scale-free compact routing schemes in networks of low doubling dimension

Distributed algorithms for multicommodity flow problems via approximate steepest descent framework

Network sketching or: "How Much Geometry Hides in Connectivity?--Part II"

Line-of-sight networks

All-pairs bottleneck paths in vertex weighted graphs

Finding a heaviest triangle is not harder than matrix multiplication

Matrix-vector multiplication in sub-quadratic time: (some preprocessing required)

A linear work, $O(n^{1/6})$ time, parallel algorithm for solving planar Laplacians

Fast computation of power series solutions of systems of differential equations

Combinatorial algorithms for web search engines: three success stories

k-means++: the advantages of careful seeding

Spectral clustering with limited independence

A rigorous analysis of population stratification with limited data

Restricted strip covering and the sensor cover problem

Compressing rectilinear pictures and minimizing access control lists

Reconstruction using witness complexes

Geometric and topological guarantees for the WRAP reconstruction algorithm

Delaunay refinement for piecewise smooth complexes

Complexity of Delaunay triangulation for points on lower-dimensional polyhedra

On the number of tetrahedra with minimum, unit, and distinct volumes in three-space

Games of fixed rank: a hierarchy of bimatrix games

The effectiveness of Stackelberg strategies and tolls for network congestion games

Setting lower bounds on truthfulness: extended abstract

An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem

A lower bound for scheduling mechanisms

The independent even factor problem

Fractional packing in ideal clutters

Half integral packing, Erdős-Posá-property and graph minors

Harmonic algorithm for 3-dimensional strip packing problem

Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems

Quantum algorithms for Simon's problem over general groups

Quantum algorithm for a generalized hidden shift problem

The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits

Correlation decay and deterministic FPTAS for counting list-colorings of a graph

Counting good truth assignments of random k-SAT formulae

Approximation algorithms for node-weighted buy-at-bulk network design

Approximation algorithms for prize collecting forest problems with submodular penalty functions

A polynomial-time approximation scheme for Steiner tree in planar graphs

Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract

Approximation algorithms for stochastic and risk-averse optimization

On testable properties in bounded degree graphs

Content Provider	ACM Digital Library
Author	Sohler, Christian Czumaj, Artur
Abstract	We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is $O(1/log^{2}$ n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property Π to be testable for a graph family F if for every graph G ε F, in time independent of the size of G we can distinguish between the case when G satisfies property Π and when it is far from every graph satisfying property Π. In this paper we prove that In the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs. As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.
Starting Page	494
Ending Page	501
Page Count	8
File Format	PDF
ISBN	9780898716245
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-01-07
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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