Results 31 to 40 of about 1,033 (146)
On the Path-Width of Integer Linear Programming [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it.
Constantin Enea +3 more
doaj +1 more source
From Pathwidth to Connected Pathwidth [PDF]
, 2011 It is proven that the connected pathwidth of any graph G is at most 2*pw(G)+1, where pw(G) is the pathwidth of G. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width k computes a connected path ...
Dariusz Dereniowski +1 more
core +1 more source
Pathwidth, trees, and random embeddings [PDF]
Combinatorica, 2013 We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair states that for every minor-closed family of graphs $F$, there is a constant $c(F)$ such that the ...
James R. Lee, Anastasios Sidiropoulos
openaire +5 more sources
On the Pathwidth of Almost Semicomplete Digraphs [PDF]
, 2015 We call a digraph {\em $h$-semicomplete} if each vertex of the digraph has at most $h$ non-neighbors, where a non-neighbor of a vertex $v$ is a vertex $u \neq v$ such that there is no edge between $u$ and $v$ in either direction. This notion generalizes that of semicomplete digraphs which are $0$-semicomplete and tournaments which are semicomplete and ...
Kenta Kitsunai +2 more
openaire +4 more sources
The treewidth and pathwidth of hypercubes
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
L. Sunil Chandran, Telikepalli Kavitha
openaire +1 more source
Approximation of pathwidth of outerplanar graphs [PDF]
Journal of Algorithms, 2001 Summary: There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph \(G\), finds a path decomposition of \(G\) of pathwidth at most twice the pathwidth of \(G\) plus one.
Hans L. Bodlaender, Fedor V. Fomin
openaire +6 more sources
Grundy Distinguishes Treewidth from Pathwidth
SIAM Journal on Discrete Mathematics, 2022 Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status ...
Rémy Belmonte +4 more
openaire +4 more sources
First Order Logic on Pathwidth Revisited Again [PDF]
Logical Methods in Computer ScienceCourcelle's celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each
Michael Lampis
doaj +1 more source
Linear Datalog and Bounded Path Duality of Relational Structures [PDF]
Logical Methods in Computer Science, 2005 In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs.
Victor Dalmau
doaj +1 more source
On the treewidth of triangulated 3-manifolds
Journal of Computational Geometry, 2019 In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is.
Kristóf Huszár +2 more
doaj +1 more source