Results 11 to 20 of about 1,532 (205)
An Improvement of Reed’s Treewidth Approximation [PDF]
Journal of Graph Algorithms and Applications, 2022 We present a new approximation algorithm for the treewidth problem which finds an upper bound on the treewidth and constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed's classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis
Mahdi Belbasi, Martin Fürer
openalex +3 more sources
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
Constant Congestion Brambles [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the ...
Meike Hatzel +3 more
doaj +1 more source
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, Nidhi Purohit
openalex +8 more sources
Treewidth: Computational Experiments [PDF]
Electronic Notes in Discrete Mathematics, 2001 Many N/P-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for many ...
Koster,Arie M.C.A. +2 more
openaire +8 more sources
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
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
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
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