Results 81 to 90 of about 4,791 (239)
Counting Linear Extensions: Parameterizations by Treewidth. [PDF]
Algorithmica, 2019 We consider the # P -complete problem of counting the number of linear extensions of a poset ( # LE ) ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of # LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations ...
Eiben E, Ganian R, Kangas K, Ordyniak S.
europepmc +9 more sources
Between Treewidth and Clique-Width [PDF]
Algorithmica, 2014 Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but ...
Sigve Hortemo Sæther, Jan Arne Telle
openaire +3 more sources
Practical Access to Dynamic Programming on Tree Decompositions
Algorithms, 2019 Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood.
Max Bannach, Sebastian Berndt
doaj +1 more source
On Endomorphism Universality of Sparse Graph Classes
Journal of Graph Theory, Volume 110, Issue 2, Page 223-244, October 2025.ABSTRACT We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product,
Kolja Knauer, Gil Puig i Surroca
wiley +1 more source
Tree-width and large grid minors in planar graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2011 Graphs and ...
Alexander Grigoriev
doaj +1 more source
Tight Distance Query Reconstruction for Trees and Graphs Without Long Induced Cycles
Random Structures &Algorithms, Volume 66, Issue 4, July 2025.ABSTRACT Given access to the vertex set V$$ V $$ of a connected graph G=(V,E)$$ G=\left(V,E\right) $$ and an oracle that given two vertices u,v∈V$$ u,v\in V $$, returns the shortest path distance between u$$ u $$ and v$$ v $$, how many queries are needed to reconstruct E$$ E $$?
Paul Bastide, Carla Groenland
wiley +1 more source
Grundy Distinguishes Treewidth from Pathwidth
SIAM Journal on Discrete Mathematics, 2022 Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status ...
Rémy Belmonte +4 more
openaire +4 more sources
Structural properties of graph products
Journal of Graph Theory, Volume 109, Issue 2, Page 107-136, June 2025.Abstract Dujmovć, Joret, Micek, Morin, Ueckerdt, and Wood established that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. Motivated by this result, this paper systematically studies various structural properties of cartesian, direct and strong products.
Robert Hickingbotham, David R. Wood
wiley +1 more source
Information and Computation, 2017 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Müller, Moritz, Szeider, Stefan
openaire +1 more source
Mathematics, 2023 Considering the worst-case scenario, the junction-tree algorithm remains the most general solution for exact MAP inference with polynomial run-time guarantees.
Alexander Bauer +2 more
doaj +1 more source