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
Alber et al. A refined search tree technique for dominating set on planar graphs
Broersma et al. Closure concepts: a survey
Guo et al. Improved algorithms for bicluster editing
Housni An efficient algorithm for enumerating all minimal paths of a graph
Kern et al. Contracting to a longest path in H-free graphs
Czyzowicz et al. Searching for a black hole in tree networks
Heggernes et al. Interval completion with few edges
Peng et al. Graph searching on some subclasses of chordal graphs
El-Mallah et al. On two dual classes of planar graphs
Belmonte et al. Characterizing graphs of small carving-width
Georgiadis et al. Faster computation of 3-edge-connected components in digraphs
Georgiadis et al. Incremental $2 $-Edge-Connectivity in Directed Graphs
Karakashian et al. An algorithm for generating all connected subgraphs with k vertices of a graph
Jansson et al. Inferring a level-1 phylogenetic network from a dense set of rooted triplets
Georgiadis et al. All-Pairs 2-Reachability in $\mathcal {O}(n^{\omega}\log n) $ Time
Brandenburg et al. Finite graph automata for linear and boundary graph languages
Gopalan et al. On constructing three edge independent spanning trees
Abueida et al. Hamiltonian spider intersection graphs are cycle extendable