Results 41 to 50 of about 13,679 (262)
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
Treewidth of Grid Subsets [PDF]
Combinatorica, 2017 15 pages, no ...
Sergey Norin +2 more
openaire +2 more sources
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
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
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
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
Metric Dimension Parameterized By Treewidth [PDF]
Algorithmica, 2021 AbstractA resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer.
Édouard Bonnet +2 more
openaire +7 more sources
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
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