Results 31 to 40 of about 306 (178)
Contraction and Treewidth Lower Bounds
Journal of Graph Algorithms and Applications, 2006 Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree.
Hans Bodlaender +2 more
doaj +1 more source
Answer Counting under Guarded TGDs [PDF]
Logical Methods in Computer Science, 2023 We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language ...
Cristina Feier +2 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
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
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
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
Journal of Graph Algorithms and Applications, 2018 We investigate crossing minimization for $1$-page and $2$-page book drawings. We show that computing the $1$-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing $2$-page planarity is fixed-parameter ...
Michael Bannister, David Eppstein
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
On Low Treewidth Graphs and Supertrees
Journal of Graph Algorithms and Applications, 2015 Compatibility of unrooted phylogenetic trees is a well studied problem in phylogenetics. It asks to determine whether for a set of k input trees T1,...,Tk there exists a larger tree (called a supertree) that contains the topologies of all k input trees ...
Alexander Grigoriev +2 more
doaj +1 more source
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hans L. Bodlaender, Arie M. C. A. Koster
openaire +5 more sources
Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width [PDF]
Logical Methods in Computer Science, 2013 Parity games are a much researched class of games in NP intersect CoNP that are not known to be in P. Consequently, researchers have considered specialised algorithms for the case where certain graph parameters are small.
John Fearnley, Sven Schewe
doaj +1 more source