Results 31 to 40 of about 11,104 (228)
Tuza's Conjecture for Threshold Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including
Marthe Bonamy +6 more
doaj +1 more source
Approximating acyclicity parameters of sparse hypergraphs [PDF]
, 2008 The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity.
Fomin, Fedor V. +2 more
core +5 more sources
Patterns with Bounded Treewidth [PDF]
Information and Computation, 2012 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Reidenbach, Daniel, Schmid, Markus L.
openaire +2 more sources
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
A structural approach to kernels for ILPs: Treewidth and Total Unimodularity [PDF]
, 2015 Kernelization is a theoretical formalization of efficient preprocessing for NP-hard problems. Empirically, preprocessing is highly successful in practice, for example in state-of-the-art ILP-solvers like CPLEX.
A. Atamtürk +7 more
core +2 more sources
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
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs [PDF]
, 2010 The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bod90],[YBFT99].
Das, Bireswar +2 more
core +5 more sources
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