Nothing Special   »   [go: up one dir, main page]

Babu et al., 2016 - Google Patents

Every property of outerplanar graphs is testable

Babu et al., 2016

View PDF
Document ID
900784224721707512
Author
Babu J
Khoury A
Newman I
Publication year
Publication venue
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

External Links

Snippet

A D-disc around a vertex v of a graph G=(V, E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most epsilon n edges, by a set of …
Continue reading at drops.dagstuhl.de (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30958—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30587—Details of specialised database models
    • G06F17/30589—Hierarchical databases, e.g. IMS, LDAP data stores, Lotus Notes
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30705—Clustering or classification
    • G06F17/3071—Clustering or classification including class or cluster creation or modification
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G06F17/5009—Computer-aided design using simulation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N99/00—Subject matter not provided for in other groups of this subclass
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication Publication Date Title
Jozsa Quantum algorithms and the Fourier transform
Feldman et al. Sample complexity bounds on differentially private learning via communication complexity
Chitnis et al. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams
Montanaro Quantum walk speedup of backtracking algorithms
Jayaram et al. Perfect l_p sampling in a data stream
McGregor et al. Better algorithms for counting triangles in data streams
Gishboliner et al. A generalized Turán problem and its applications
Ahn et al. Graph sketches: sparsification, spanners, and subgraphs
Jha et al. Testing and reconstruction of Lipschitz functions with applications to data privacy
Babu et al. Every property of outerplanar graphs is testable
Cai et al. # BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Elek Finite graphs and amenability
Loizou et al. Accelerated gossip via stochastic heavy ball method
Henzinger et al. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
Anagnostopoulos et al. Community detection on evolving graphs
Dominguez et al. Mutual information for the sparse stochastic block model
Behnezhad et al. Single-pass streaming algorithms for correlation clustering
Behnezhad et al. Sublinear time algorithms and complexity of approximate maximum matching
Assadi et al. Tight bounds on the round complexity of the distributed maximum coverage problem
Bshouty et al. Learning DNF from random walks
Newman et al. New sublinear algorithms and lower bounds for LIS estimation
Gao et al. Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex
Chen et al. Streaming euclidean mst to a constant factor
Bezáková et al. Lower bounds for testing graphical models: Colorings and antiferromagnetic ising models
Demaine et al. Structural sparsity of complex networks: Random graph models and linear algorithms