Results 51 to 60 of about 4,791 (239)
Journal of Combinatorial Theory, Series B, 2005 Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \(\text{tw}(G)\) of a graph \(G\), giving a lower bound in terms of the girth \(g(G)\) and average degree \(d(G)\). They show that \[ \text{tw}(G)\geq c {1\over g(G)+1} (d(G)-1)^
Chandran, L., Subramanian, C.
openaire +3 more sources
A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth
Algorithms, 2019 We present an algorithm selection framework based on machine learning for the exact computation of treewidth, an intensively studied graph parameter that is NP-hard to compute.
Borislav Slavchev +2 more
doaj +1 more source
Tractable Abstract Argumentation via Backdoor-Treewidth
AAAI Conference on Artificial Intelligence, 2022 Argumentation frameworks (AFs) are a core formalism in the field of formal argumentation. As most standard computational tasks regarding AFs are hard for the first or second level of the Polynomial Hierarchy, a variety of algorithmic approaches to ...
Wolfgang Dvořák +5 more
semanticscholar +1 more source
Computing Treewidth on the GPU [PDF]
arXiv, 2017 We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an $O^*(2^{n})$-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach.
Tom C. van der Zanden +1 more
openalex +6 more sources
Stable gonality is computable [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Stable gonality is a multigraph parameter that measures the complexity of a graph. It is defined using maps to trees. Those maps, in some sense, divide the edges equally over the edges of the tree; stable gonality asks for the map with the minimum number
Ragnar Groot Koerkamp +1 more
doaj +1 more source
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$.
Zongwen Bai, Jianhua Tu, Yongtang Shi
doaj +1 more source
Journal of Combinatorial Theory, Series B, 2007 25 ...
Chandran, LS, Sivadasan, N
openaire +2 more sources
Threshold Treewidth and Hypertree Width [PDF]
Journal of Artificial Intelligence Research, 2020 Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction Problem (CSP). When either of these parameters is bounded by a constant, then CSP becomes solvable in polynomial time. However, here the order of the polynomial in the running time depends on the width, and this is known
Ganian, Robert +3 more
openaire +2 more sources
Tree-width for first order formulae [PDF]
Logical Methods in Computer Science, 2012 We introduce tree-width for first order formulae \phi, fotw(\phi). We show that computing fotw is fixed-parameter tractable with parameter fotw. Moreover, we show that on classes of formulae of bounded fotw, model checking is fixed parameter tractable ...
Isolde Adler, Mark Weyer
doaj +1 more source
Optimizing tree decompositions in MSO [PDF]
Logical Methods in Computer Science, 2022 The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the ...
Mikołaj Bojańczyk, Michał Pilipczuk
doaj +1 more source