Results 41 to 50 of about 2,730 (147)
Exclusive graph searching vs. pathwidth [PDF]
Information and Computation, 2017 In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task.
Markou, Euripides +2 more
openaire +3 more sources
On the width of complicated JSJ decompositions [PDF]
39th International Symposium on Computational Geometry (SoCG
2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 129,
pg. 42:1-42:18, 2023, 2023 Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all ...
arxiv +1 more source
The Pebble-Relation Comonad in Finite Model Theory [PDF]
Logical Methods in Computer ScienceThe pebbling comonad, introduced by Abramsky, Dawar and Wang, provides a categorical interpretation for the k-pebble games from finite model theory.
Yoàv Montacute, Nihil Shah
doaj +1 more source
Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]
Logical Methods in Computer ScienceWe show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj +1 more source
Tree-decompositions of small pathwidth
Electronic Notes in Discrete Mathematics, 2004 AbstractMotivated by the desire to speed up dynamic programming algorithms for graphs of bounded treewidth, we initiate a study of the tradeoff between width and pathwidth of tree-decompositions. We therefore investigate the catwidth parameter catw(G) which is the minimum width of any tree-decomposition (T,X) of a graph G when the pathwidth pw(T) of ...
Jan Arne Telle
openalex +4 more sources
EPG-representations with small grid-size [PDF]
, 2017 In an EPG-representation of a graph $G$ each vertex is represented by a path in the rectangular grid, and $(v,w)$ is an edge in $G$ if and only if the paths representing $v$ an $w$ share a grid-edge. Requiring paths representing edges to be x-monotone or,
A Asinowski +11 more
core +2 more sources
Majority constraints have bounded pathwidth duality [PDF]
European Journal of Combinatorics, 2008 We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain ...
Víctor Dalmau, Andrei Krokhin
openalex +4 more sources
FPT is Characterized by Useful Obstruction Sets [PDF]
, 2013 Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable, obstruction sets and efficient order tests is not just one way of ...
Fellows, Michael R., Jansen, Bart M. P.
core +1 more source
2-Layer Graph Drawings with Bounded Pathwidth [PDF]
arXiv, 2022 We determine which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.
arxiv
The Firefighter Problem: A Structural Analysis [PDF]
, 2014 We consider the complexity of the firefighter problem where b>=1 firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al.,2007) and on trees of bounded degree b+3
A King +16 more
core +3 more sources