Results 121 to 130 of about 4,776 (247)
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
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth [PDF]
ACM-SIAM Symposium on Discrete Algorithms, 2022 Marthe Bonamy +7 more
semanticscholar +1 more source
Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth [PDF]
Discrete Mathematics, 2022 Chunqi Liu
semanticscholar +1 more source
Cop-width, flip-width and strong colouring numbers [PDF]
Discrete Mathematics & Theoretical Computer ScienceCop-width and flip-width are new families of graph parameters introduced by Toru\'nczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and twin-width.
Robert Hickingbotham
doaj +1 more source
Journal of Graph Theory, 2016 AbstractTreewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This article surveys several graph parameters tied to treewidth, including separation number, tangle number, well‐linked number, and Cartesian tree product number.
Daniel J. Harvey, David R. Wood
openaire +4 more sources
Fast simulation of planar Clifford circuits [PDF]
QuantumA general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally ...
David Gosset +3 more
doaj +1 more source
Causal Unit Selection using Tractable Arithmetic Circuits
Proceedings of the International Florida Artificial Intelligence Research Society ConferenceThe unit selection problem aims to find objects, called units, that optimize a causal objective function which describes the objects' behavior in a causal context (e.g., selecting customers who are about to churn but would most likely change their mind ...
Haiying Huang, Adnan Darwiche
doaj +1 more source
Minimum Fill-In and Treewidth for Graphs Modularly Decomposable into Chordal Graphs [PDF]
, 1998 Elias Dahlhaus
openalex +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
Treewidth versus clique number. II. Tree-independence number [PDF]
J. Comb. Theory B, 2021 Clément Dallard +2 more
semanticscholar +1 more source