Results 61 to 70 of about 1,027 (141)

On the pathwidth of chordal graphs

Discrete Applied Mathematics, 1993
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire   +2 more sources

On first-order transductions of classes of graphs [PDF]

Logical Methods in Computer Science
We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic.
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz   +3 more
doaj   +1 more source

A 3-approximation for the pathwidth of Halin graphs

Journal of Discrete Algorithms, 2004
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Fedor V. Fomin, Dimitrios M. Thilikos
openaire   +5 more sources

The Price of Upwardness [PDF]

Discrete Mathematics & Theoretical Computer Science
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the
Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, Alexander Wolff   +10 more
doaj   +1 more source

Superpatterns and Universal Point Sets

Journal of Graph Algorithms and Applications, 2014
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.
Michael Bannister, Zhanpeng Cheng, William Devanny, David Eppstein   +3 more
doaj   +1 more source

Strong-mixed searching and pathwidth [PDF]

Journal of Combinatorial Optimization, 2006
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire   +2 more sources

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs [PDF]

Journal of Algorithms, 1996
Summary: We give, for all constants \(k\), \(\ell\), explicit algorithms that, given a graph \(G=(V,E)\) with a tree-decomposition of \(G\) with treewidth at most \(\ell\), decide whether the treewidth (or pathwidth) of \(G\) is at most \(k\), and, if so, find a tree-decomposition (or path-decomposition) of \(G\) of width at most \(k\), and that use ...
Hans L. Bodlaender, Ton Kloks
openaire   +4 more sources

Stack Number, Track Number, and Layered Pathwidth

, 2020
In this thesis, we consider three parameters associated with graphs : stack number, track number, and layered pathwidth. Our first result is to show that the stack number of any graph is at most 4 times its layered pathwidth.
Yelle, Céline
core   +1 more source

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, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil   +3 more
doaj   +1 more source

Grundy Distinguishes Treewidth from Pathwidth [PDF]

, 2020
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 ...
Lampis, Michael, Belmonte, Rémy, Mitsou, Valia, Otachi, Yota, Kim, Eun Jung   +4 more
core   +1 more source