Results 31 to 40 of about 4,791 (239)
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
Treewidth, Circle Graphs, and Circular Drawings [PDF]
SIAM Journal on Discrete Mathematics, 2022 A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'.
Robert Hickingbotham +3 more
semanticscholar +1 more source
Turbocharging Treewidth Heuristics [PDF]
Algorithmica, 2018 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Gaspers, S +4 more
openaire +3 more sources
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
Twin-width can be exponential in treewidth [PDF]
J. Comb. Theory B, 2022 For any small positive real $\varepsilon$ and integer $t>\frac{1}{\varepsilon}$, we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2^{(1-\varepsilon) t}$.
Édouard Bonnet, Hugues Déprés
semanticscholar +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
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
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