Optimal listing of cycles and st-paths in undirected graphs
The classical problem of efficiently listing all the simple cycles in a graph has been studied
since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most …
since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most …
Enumeration of enumeration algorithms
K Wasa - arXiv preprint arXiv:1605.05102, 2016 - arxiv.org
arXiv:1605.05102v2 [cs.DS] 25 May 2016 Page 1 arXiv:1605.05102v2 [cs.DS] 25 May 2016
Enumeration of Enumeration Algorithms Kunihiro Wasa∗ May 26, 2016 Abstract In this paper …
Enumeration of Enumeration Algorithms Kunihiro Wasa∗ May 26, 2016 Abstract In this paper …
An efficient algorithm for enumerating chordless cycles and chordless paths
A chordless cycle (induced cycle) C of a graph is a cycle without any chord, meaning that
there is no edge outside the cycle connecting two vertices of the cycle. A chordless path is …
there is no edge outside the cycle connecting two vertices of the cycle. A chordless path is …
Amortized-delay algorithm for listing chordless cycles in undirected graphs
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 …
and distinguished role in graph theory. Motivated also by previous work on the classical …
Analysis and enumeration
A Marino - Algorithms for biological graphs. This pricewinning …, 2015 - Springer
The aim of enumeration is listing all the feasible solutions of a given problem: this is
particularly useful whenever the goal of the problem is not clear and we need to check all its …
particularly useful whenever the goal of the problem is not clear and we need to check all its …
Efficient enumeration of chordless cycles
ES Dias, D Castonguay, H Longo… - arXiv preprint arXiv …, 2013 - arxiv.org
In a finite undirected simple graph, a {\it chordless cycle} is an induced subgraph which is a
cycle. We propose two algorithms to enumerate all chordless cycles of such a graph …
cycle. We propose two algorithms to enumerate all chordless cycles of such a graph …
Compactly generating all satisfying truth assignments of a Horn formula
M Wild - Journal on satisfiability, Boolean modeling and …, 2012 - content.iospress.com
While it was known that all models of a Horn formula can be generated in output-polynomial
time, here we present an explicit algorithm as opposed to the rather vague oracle-scheme …
time, here we present an explicit algorithm as opposed to the rather vague oracle-scheme …
Counting or producing all fixed cardinality transversals
M Wild - Algorithmica, 2014 - Springer
Counting or Producing All Fixed Cardinality Transversals | SpringerLink Skip to main content
Advertisement SpringerLink Log in Menu Find a journal Publish with us Search Cart 1.Home …
Advertisement SpringerLink Log in Menu Find a journal Publish with us Search Cart 1.Home …
[PDF][PDF] An algorithm for generating all connected subgraphs with k vertices of a graph
In this paper, we introduce a new algorithm ConSubg (k, G) for computing all the connected
subgraphs of a fixed size k of a graph G. Con-Subg exploits the structure of the graph to …
subgraphs of a fixed size k of a graph G. Con-Subg exploits the structure of the graph to …
[PDF][PDF] Enumerating chordless circuits in directed graphs
R Bisdorff - ORBEL 24 24th Belgian Conference on Operations …, 2010 - orbilu.uni.lu
We introduce and discuss an algorithm using O (p) time and O (n (n+ m)) space for
enumerating the m⩾ 0 chordless circuits in a digraph of order n and containing p chordless …
enumerating the m⩾ 0 chordless circuits in a digraph of order n and containing p chordless …