Results 71 to 80 of about 1,033 (146)

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

Derivatives on Graphs for the Positive Calculus of Relations with Transitive Closure [PDF]

Logical Methods in Computer Science
We prove that the equational theory of the positive calculus of relations with transitive closure (PCoR*) is EXPSPACE-complete. Here, PCoR* terms consist of the following standard operators on binary relations: identity, empty, universality, union ...
Yoshiki Nakamura
doaj   +1 more source

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

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

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

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

Narrowness, pathwidth, and their application in natural language processing [PDF]

, 1992
In the syntactic theory of Tesnière (1959) the structural description of sentences are given as graphs. We discuss how the graph-theoretic concept of pathwidth is relevant in this approach.
Tuza, Zsolt, Kornai, András
core   +1 more source

The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations

Algorithms
Tree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded tree-width or bounded path-width. In this work, we study the behavior of tree-width and path-width
Frank Gurski, Robin Weishaupt
doaj   +1 more source