Results 41 to 50 of about 4,776 (247)
Embedding phylogenetic trees in networks of low treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods ...
Leo van Iersel +2 more
doaj +1 more source
Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective
Mathematics, 2023 The clique transversal problem and its variants have garnered significant attention in the last two decades due to their practical applications in communication networks, social-network theory and transceiver placement for cellular telephones.
Chuan-Min Lee
doaj +1 more source
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 +3 more sources
Constrained Connectivity in Bounded X-Width Multi-Interface Networks
Algorithms, 2020 As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere.
Alessandro Aloisio, Alfredo Navarra
doaj +1 more source
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
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2021 The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs.
Jacob Focke +2 more
semanticscholar +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 ...
Chatterjee, Krishnendu +2 more
openaire +3 more sources
Clique‐width: Harnessing the power of atoms
Journal of Graph Theory, Volume 104, Issue 4, Page 769-810, December 2023., 2023 Abstract Many NP‐complete graph problems are polynomial‐time solvable on graph classes of bounded clique‐width. Several of these problems are polynomial‐time solvable on a hereditary graph class G ${\mathscr{G}}$ if they are so on the atoms (graphs with no clique cut‐set) of G ${\mathscr{G}}$.
Konrad K. Dabrowski +4 more
wiley +1 more source
Patterns with Bounded Treewidth [PDF]
Information and Computation, 2012 We show that any parameter of patterns that is an upper bound for the treewidth of appropriate encodings of patterns as relational structures, if restricted to a constant, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify a new such parameter, called the scope coincidence degree.
Markus L. Schmid, Daniel Reidenbach
openaire +2 more sources
Vertex covering with capacitated trees
Networks, Volume 81, Issue 2, Page 253-277, March 2023., 2023 Abstract The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs.
Ralf Borndörfer +2 more
wiley +1 more source