[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Cai et al., 1993 - Google Patents

Degree-bounded spanners

Cai et al., 1993

Document ID
14062210872804973039
Author
Cai L
Keil J
Publication year
Publication venue
Parallel Processing Letters

External Links

Snippet

Given a graph G, a spanning subgraph H of G is a t-spanner if for every edge xy of G, the distance in H between x and y is at most t. Spanners have applications in communication networks, distributed systems, parallel computation, and other areas. This paper is …
Continue reading at www.worldscientific.com (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/50—Computer-aided design
    • G06F17/5009—Computer-aided design using simulation
    • 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/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—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/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/10—Complex mathematical operations
    • 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
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc

Similar Documents

Publication Publication Date Title
Cai NP-completeness of minimum spanner problems
Garg et al. On the computational complexity of upward and rectilinear planarity testing
Saleur Polymers and percolation in two dimensions and twisted N= 2 supersymmetry
Teplyaev Spectral analysis on infinite Sierpiński gaskets
Barnard et al. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems
Garg et al. On the computational complexity of upward and rectilinear planarity testing
Agarwal et al. Parametric and kinetic minimum spanning trees
Papasoglu et al. Quasi-isometries between groups with infinitely many ends
Brandstädt et al. The complexity of some problems related to graph 3-colorability
Allender et al. A first-order isomorphism theorem
Ortega The homology of the Katsura–Exel–Pardo groupoid
Jacobsen Conformal field theory applied to loop models
Megson et al. Honeycomb tori are Hamiltonian
Narayanan et al. Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees
Conrad A q-analogue of Mahler expansions, I
Cai et al. Degree-bounded spanners
Iwano et al. Planarity testing of doubly periodic infinite graphs
Yu Orientable vertex imprimitive complete maps
Li et al. Better approximation of diagonal-flip transformation and rotation transformation
Welsh The computational complexity of knot and matroid polynomials
Requardt Dirac operators and the calculation of the Connes metric on arbitrary (infinite) graphs
Gao et al. Novel quantum algorithms to minimize switching functions based on graph partitions
Iordanski Constructive Graph Theory: Generation Methods, Structure and Dynamic Characterization of Closed Classes of Graphs--A survey
Ross et al. Exact ordered binary decision diagram size when representing classes of symmetric functions
Hayase et al. Output-size sensitiveness of OBDD construction through maximal independent set problem