[go: up one dir, main page]

Chakraborty et al., 2019 - Google Patents

Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS

Chakraborty et al., 2019

View PDF
Document ID
6362095453514332478
Author
Chakraborty S
Satti S
Publication year
Publication venue
Journal of Combinatorial Optimization

External Links

Snippet

Following the recent trends of designing space efficient algorithms for fundamental algorithmic graph problems, we present several time-space tradeoffs for performing maximum cardinality search (MCS), stack breadth first search, and queue breadth first …
Continue reading at www.academia.edu (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/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/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/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/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • 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/30908—Information retrieval; Database structures therefor; File system structures therefor of semistructured data, the undelying structure being taken into account, e.g. mark-up language structure data
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • 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

Similar Documents

Publication Publication Date Title
Baswana et al. Dynamic DFS in undirected graphs: Breaking the o(m) barrier
Chakraborty et al. Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
Banerjee et al. Space efficient linear time algorithms for BFS, DFS and applications
Watel et al. A practical greedy approximation for the directed steiner tree problem
Wasa et al. Efficient enumeration of induced subtrees in a K-degenerate graph
Conte et al. Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
Chakraborty et al. Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
Chakraborty et al. Succinct representation for (non) deterministic finite automata
Bui-Xuan et al. Feedback vertex set on graphs of low clique-width
Eisenstat et al. The theory of elimination trees for sparse unsymmetric matrices
Baswana et al. Incremental algorithm for maintaining a DFS tree for undirected graphs
Chakraborty et al. Succinct data structures for small clique-width graphs
Bernstein et al. Maximum flow by augmenting paths in $ n^{2+ o (1)} $ time
Nakamura et al. A space-efficient algorithm for the dynamic DFS problem in undirected graphs
Bille et al. The tree inclusion problem: In optimal space and faster
Chakraborty et al. Space efficient algorithms for breadth-depth search
Boura et al. Differential analysis of the ternary hash function troika
Brankovic et al. Local routing in a tree metric 1-spanner
Bose et al. The power and limitations of static binary search trees with lazy finger
Nikolopoulos Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
Chan et al. Fully dynamic algorithms for euclidean steiner tree
Lievonen et al. Distributed binary labeling problems in high-degree graphs
Bhattacharya et al. Sampling in space restricted settings
Nigmetov et al. Distributed Computation of Persistent Cohomology
Bendahi et al. On Constrained and k Shortest Paths