Results 141 to 150 of about 2,549 (154)

Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth [PDF]

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl   +2 more
openalex   +1 more source

New algorithms for pathwidth computation

, 2004
Ming Li, Nathaniel Dean
openalex   +1 more source

Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

, 2014
David Coudert, Dorian Mazauric, Nicolas Nisse   +2 more
openalex   +1 more source

Some of the next articles are maybe not open access.

Related searches:

PATHWIDTH AND LAYERED DRAWINGS OF TREES

International Journal of Computational Geometry & Applications, 2004
An h-layer drawing of a graph G is a planar drawing of G in which each vertex is placed on one of h parallel lines and each edge is drawn as a straight line between its end-vertices. In such a drawing, we say that an edge is proper if its endpoints lie on adjacent layers, flat if they lie on the same layer and long otherwise.
openaire   +2 more sources

Pathwidth of Planar and Line Graphs

Graphs and Combinatorics, 2003
The paper studies the pathwidth \(\text{pw}(G)\) of planar graphs and proves that for any 2-connected plane graph \(G\) with pathwidth \(\text{pw}(G^*)\) of the geometric dual graph \(G^*\) of \(G\) is smaller than the pathwidth \(\text{pw}(L(G))\) of the line graph \(L(G)\) of \(G\).
openaire   +1 more source

Directed Pathwidth and Palletizers

2015
In delivery industry, bins have to be stacked-up from conveyor belts onto pallets. Given k sequences of labeled bins and a positive integer p. The goal is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto a pallet located at one of p stack-up places.
Frank Gurski, Jochen Rethmann, Egon Wanke   +2 more
openaire   +1 more source

Approximating the pathwidth of outerplanar graphs

Information Processing Letters, 1998
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Govindan, Rajeev, Langston, Michael A., Yan, Xudong   +2 more
openaire   +2 more sources

Online Problems, Pathwidth, and Persistence

2004
We explore the effects of using graph width metrics as restrictions on the input to online problems. It seems natural to suppose that, for graphs having some form of bounded width, good online algorithms may exist for a number of natural problems. In the work presented we concentrate on online graph coloring problems, where we restrict the allowed ...
Rodney G. Downey, Catherine McCartin
openaire   +1 more source

Revisiting Space in Proof Complexity: Treewidth and Pathwidth

2013
So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space.
Moritz Mýller, Stefan Szeider
openaire   +3 more sources

A Linear Algorithm for the Pathwidth of Trees

1990
The pathwidth is a graph parameter only recently studied but closely related to other characteristics of graphs like tree, band- or cutwidth, interval thickness or search number ([S]). The graphs considered here are finite, undirected and simple. First the preliminaries are given. Section 2 contains our main results on the pathwidth of trees, the basis
openaire   +1 more source