Results 41 to 50 of about 609 (128)
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
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
The Bounded Pathwidth of Control-Flow Graphs
Proceedings of the ACM on Programming Languages, 2023 Pathwidth and treewidth are standard and well-studied graph sparsity parameters which intuitively model the degree to which a given graph resembles a path or a tree, respectively. It is well-known that the control-flow graphs of structured goto-free programs have a tree-like shape and bounded treewidth.
Giovanna Kobus Conrado +2 more
openaire +3 more sources
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
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
Outerplanar Obstructions for Matroid Pathwidth
Electronic Notes in Discrete Mathematics, 2011 This article appeared in a journal published by Elsevier. The attached copy is furnished to the author for internal non-commercial research and education use, including for instruction at the authors institution and sharing with colleagues. Other uses, including reproduction and distribution, or selling or licensing copies, or posting to personal ...
Koichi Yamazaki +3 more
openaire +9 more sources
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
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
Algorithms, 2018 Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen +3 more
doaj +1 more source
On Approximating Cutwidth and Pathwidth
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based
Bansal, Nikhil +2 more
openaire +2 more sources