Results 51 to 60 of about 3,161 (171)
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
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
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
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
Obstructions to within a few vertices or edges of acyclic [PDF]
, 1995 Finite obstruction sets for lower ideals in the minor order are guaranteed to exist by the Graph Minor Theorem. It has been known for several years that, in principle, obstruction sets can be mechanically computed for most natural lower ideals.
Cattell, Kevin +2 more
core +3 more sources
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs [PDF]
, 2020 The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors.
+3 more
core +3 more sources
Two Results on Layered Pathwidth and Linear Layouts [PDF]
J. Graph Algorithms Appl., 2020 Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts.
Vida Dujmovi'c, Pat Morin, Céline Yelle
semanticscholar +1 more source
The treewidth and pathwidth of hypercubes
Discrete Mathematics, 2006 AbstractThe d-dimensional hypercube, Hd, is the graph on 2d vertices, which correspond to the 2d d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by Kqd) generalizes the notion of hypercubes: The vertices correspond to the qd d-vectors where ...
L. Sunil Chandran, Telikepalli Kavitha
openaire +2 more sources
Superpatterns and Universal Point Sets [PDF]
, 2013 An old open problem in graph drawing asks for the size of a universal point set, a set of points that can be used as vertices for straight-line drawings of all n-vertex planar graphs.
A. Marcus +14 more
core +3 more sources
A linear fixed parameter tractable algorithm for connected pathwidth [PDF]
Embedded Systems and Applications, 2020 The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some ...
Mamadou Moustapha Kant'e +2 more
semanticscholar +1 more source