Composing dynamic programming tree-decomposition-based algorithms [PDF]
Discrete Mathematics & Theoretical Computer ScienceGiven two integers $\ell$ and $p$ as well as $\ell$ graph classes $\mathcal{H}_1,\ldots,\mathcal{H}_\ell$, the problems $\mathsf{GraphPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell,p)$, \break $\mathsf{VertPart}(\mathcal{H}_1, \ldots, \mathcal{H}_\ell ...
Julien Baste
doaj +1 more source
Exploiting non-constant safe memory in resilient algorithms and data structures [PDF]
, 2015 We extend the Faulty RAM model by Finocchi and Italiano (2008) by adding a safe memory of arbitrary size $S$, and we then derive tradeoffs between the performance of resilient algorithmic techniques and the size of the safe memory.
DE STEFANI, LORENZO +1 more
core +2 more sources
Damage identification in structural health monitoring: a brief review from its implementation to the Use of data-driven applications [PDF]
, 2020 The damage identification process provides relevant information about the current state of a structure under inspection, and it can be approached from two different points of view.
Agis Cherta, David +4 more
core +2 more sources
Destroying Multicolored Paths and Cycles in Edge-Colored Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 We study the computational complexity of $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion. In these problems, one is given a $c$-edge-colored graph and wants to destroy all induced $c$-colored paths or cycles, respectively, on $\ell ...
Nils Jakob Eckstein +3 more
doaj +1 more source
Tree Contraction, Connected Components, Minimum Spanning Trees: a GPU Path to Vertex Fitting [PDF]
, 2014 Standard parallel computing operations are considered in the context of algorithms for solving 3D graph problems which have applications, e.g., in vertex finding in HEP.
Hobson, PR, Lopes, RHC, Reid, ID
core +1 more source
Why almost all satisfiable $k$-CNF formulas are easy [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 Finding a satisfying assignment for a $k$-CNF formula $(k \geq 3)$, assuming such exists, is a notoriously hard problem. In this work we consider the uniform distribution over satisfiable $k$-CNF formulas with a linear number of clauses (clause-variable ...
Amin Coja-Oghlan +2 more
doaj +1 more source
Prospects and limitations of full-text index structures in genome analysis [PDF]
, 2012 The combination of incessant advances in sequencing technology producing large amounts of data and innovative bioinformatics approaches, designed to cope with this data flood, has led to new interesting results in the life sciences.
Dawyndt, Peter +3 more
core +2 more sources
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Graphs and ...
Serge Gaspers, Mathieu Liedloff
doaj +1 more source
Who Learns Better Bayesian Network Structures: Accuracy and Speed of Structure Learning Algorithms [PDF]
, 2019 Three classes of algorithms to learn the structure of Bayesian networks from data are common in the literature: constraint-based algorithms, which use conditional independence tests to learn the dependence structure of the data; score-based algorithms ...
Graafland, Catharina Elisabeth +2 more
core +2 more sources
Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 In a barter exchange market, agents bring items and seek to exchange their items with one another. Agents may agree to a k-way exchange involving a cycle of k agents.
Timothy Highley, Hoang Le
doaj +1 more source