Results 31 to 40 of about 5,860 (222)
Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth [PDF]
Advances in Combinatorics, 2021 A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$-_free_ if no induced subgraph of $G$ is ...
Tara Abrishami +3 more
semanticscholar +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
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
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
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
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
Tractable Abstract Argumentation via Backdoor-Treewidth
AAAI Conference on Artificial Intelligence, 2022 Argumentation frameworks (AFs) are a core formalism in the field of formal argumentation. As most standard computational tasks regarding AFs are hard for the first or second level of the Polynomial Hierarchy, a variety of algorithmic approaches to ...
Wolfgang Dvořák +5 more
semanticscholar +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
Clan embeddings into trees, and low treewidth graphs [PDF]
Symposium on the Theory of Computing, 2021 In low distortion metric embeddings, the goal is to embed a host “hard” metric space into a “simpler” target space while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric.
Arnold Filtser, Hung Le
semanticscholar +1 more source
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