Results 41 to 50 of about 11,505 (254)
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
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
On the dimension of posets with cover graphs of treewidth $2$ [PDF]
, 2016 In 1977, Trotter and Moore proved that a poset has dimension at most $3$ whenever its cover graph is a forest, or equivalently, has treewidth at most $1$.
Joret, Gwenaël +4 more
core +3 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
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth [PDF]
, 2014 We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$, or determines whether $G_1$ and $G_2$ are isomorphic.
Lokshtanov, Daniel +3 more
core +2 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
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
Treewidth and Hyperbolicity of the Internet [PDF]
2011 IEEE 10th International Symposium on Network Computing and Applications, 2011 We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level.
de Montgolfier, Fabien +2 more
openaire +4 more sources
Parameterized Complexity of Equitable Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\left\lfloor n/k \right\rfloor$ or $\left\lceil n/k \right\rceil$ times.
Guilherme de C. M. Gomes +2 more
doaj +1 more source