Results 31 to 40 of about 278 (179)
Journal of Combinatorial Theory, Series B, 2007 25 ...
Chandran, LS, Sivadasan, N
openaire +2 more sources
On Supergraphs Satisfying CMSO Properties [PDF]
Logical Methods in Computer Science, 2021 Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $\varphi$, a positive integer $t$, and a ...
Mateus de Oliveira Oliveira
doaj +1 more source
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Algorithms, 2021 Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been ...
Johannes K. Fichte +3 more
doaj +1 more source
Information and Computation, 2017 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Moritz Müller, Stefan Szeider
openaire +1 more source
Drawing planar graphs with many collinear vertices
Journal of Computational Geometry, 2018 Consider the following problem: Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line drawing with $p$ collinear vertices?
Giordano Da Lozzo +4 more
doaj +1 more source
On the treewidth of triangulated 3-manifolds
Journal of Computational Geometry, 2019 In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is.
Kristóf Huszár +2 more
doaj +1 more source
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
The treewidth of smart contracts [PDF]
Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, 2019 Smart contracts are programs that are stored and executed on the Blockchain and can receive, manage and transfer money in the form of cryptocurrency units. Two important problems regarding smart contracts are formal analysis and compiler optimization. Formal analysis is extremely important, because smart contracts hold funds worth billions of dollars ...
Krishnendu Chatterjee +2 more
openaire +2 more sources
An Improvement of Reed’s Treewidth Approximation [PDF]
Journal of Graph Algorithms and Applications, 2021 We present a new approximation algorithm for the treewidth problem which finds an upper bound on the treewidth and constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed's classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis
Mahdi Belbasi, Martin Fürer
openaire +2 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