Results 1 to 10 of about 10,067 (200)
A note on domino treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c_k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c_k,d.
Hans L. Bodlaender
doaj +3 more sources
Extension Complexity, MSO Logic, and Treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments of a given MSO formula $\varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{\varphi}(G)$ that can be described by $f(|\varphi ...
Petr Kolman +2 more
doaj +1 more source
On the treewidths of graphs of bounded degree. [PDF]
PLoS ONE, 2015 In this paper, we develop a new technique to study the treewidth of graphs with bounded degree. We show that the treewidth of a graph G = (V, E) with maximum vertex degree d is at most [Formula: see text] for sufficiently large d, where C is a constant.
Yinglei Song, Menghong Yu
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
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity [PDF]
Logical Methods in Computer Science, 2019 This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity.
Dušan Knop +3 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
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
Recent Advances in Positive-Instance Driven Graph Searching
Algorithms, 2022 Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017).
Max Bannach, Sebastian Berndt
doaj +1 more source
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
The Treewidth of Induced Graphs of Conditional Preference Networks Is Small
Information, 2016 Conditional preference networks (CP-nets) are recently an emerging topic as a graphical model for compactly representing ordinal conditional preference relations on multi-attribute domains.
Jie Liu, Jinglei Liu
doaj +1 more source