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

Ferreira et al., 2014 - Google Patents

Amortized-delay algorithm for listing chordless cycles in undirected graphs

Ferreira et al., 2014

View PDF
Document ID
1476017294242021351
Author
Ferreira R
Grossi R
Rizzi R
Sacomoto G
Sagot M
Publication year
Publication venue
European Symposium on Algorithms

External Links

Snippet

Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to …
Continue reading at arxiv.org (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/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/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

Similar Documents

Publication Publication Date Title
Ferreira et al. Amortized-delay algorithm for listing chordless cycles in undirected graphs
Tedder et al. Simpler linear-time modular decomposition via recursive factorizing permutations
Wen et al. Enumerating k-vertex connected components in large graphs
Vempala et al. Factor 4/3 approximations for minimum 2-connected subgraphs
Klein et al. Solving planar k-terminal cut in time
Borradaile et al. All-pairs minimum cuts in near-linear time for surface-embedded graphs
Wasa et al. Efficient enumeration of induced subtrees in a K-degenerate graph
Housni An efficient algorithm for enumerating all minimal paths of a graph
Guo et al. Improved algorithms for bicluster editing
Broersma et al. Closure concepts: a survey
Kern et al. Contracting to a longest path in H-free graphs
Peng et al. Graph searching on some subclasses of chordal graphs
Heggernes et al. Interval completion with few edges
Czyzowicz et al. Searching for a black hole in tree networks
El-Mallah et al. On two dual classes of planar graphs
Belmonte et al. Characterizing graphs of small carving-width
Dyer et al. Counting weighted independent sets beyond the permanent
Krysta et al. Approximation algorithms for minimum size 2-connectivity problems
Georgiadis et al. Faster computation of 3-edge-connected components in digraphs
Coudert et al. A distributed algorithm for computing the node search number in trees
Karakashian et al. An algorithm for generating all connected subgraphs with k vertices of a graph
Georgiadis et al. Incremental $2 $-Edge-Connectivity in Directed Graphs
Jansson et al. Inferring a level-1 phylogenetic network from a dense set of rooted triplets
Bazgan et al. Complexity of most vital nodes for independent set in graphs related to tree structures
Brandenburg et al. Finite graph automata for linear and boundary graph languages