Results 61 to 70 of about 11,104 (228)
Intersection Dimension and Graph Invariants
Discussiones Mathematicae Graph Theory, 2021 We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at
Aravind N.R., Subramanian C.R.
doaj +1 more source
An Algorithmic Metatheorem for Directed Treewidth [PDF]
, 2015 The notion of directed treewidth was introduced by Johnson, Robertson, Seymour and Thomas [Journal of Combinatorial Theory, Series B, Vol 82, 2001] as a first step towards an algorithmic metatheory for digraphs.
Oliveira, Mateus de Oliveira
core
Space Saving by Dynamic Algebraization
, 2014 Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth.
A. Björklund +16 more
core +1 more source
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
Perfect Matching Under Precedence Constraints
Networks, Volume 87, Issue 2, Page 175-190, March 2026.ABSTRACT In this article, we motivate and define variants of perfect matching under precedence constraints where a perfect matching is built incrementally and precedence constraints ensure that an edge may only be added to the matching if the edge's predecessor vertices have already been covered.
Christina Büsing, Corinna Mathwieser
wiley +1 more source
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 the k-rainbow domination in graphs with bounded tree-width
Electronic Journal of Graph Theory and Applications, 2021 Given a positive integer k and a graph G = (V, E), a function f from V to the power set of Ik is called a k-rainbow function if for each vertex v ∈ V, f(v)=∅ implies ∪u ∈ N(v)f(u)=Ik where N(v) is the set of all neighbors of vertex v and Ik = {1, …, k ...
M. Alambardar Meybodi +3 more
doaj +1 more source
First-order queries on classes of structures with bounded expansion [PDF]
Logical Methods in Computer Science, 2020 We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor.
Wojtek Kazana, Luc Segoufin
doaj +1 more source
Size‐Ramsey Numbers of Structurally Sparse Graphs
Random Structures &Algorithms, Volume 68, Issue 2, March 2026.ABSTRACT Size‐Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erdős, Faudree, Rousseau, and Schelp in 1978. Research has mainly focused on the size‐Ramsey numbers of n$$ n $$‐vertex graphs with constant maximum degree Δ$$ \Delta $$.
Nemanja Draganić +4 more
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