Results 121 to 128 of about 609 (128)
Some of the next articles are maybe not open access.
Approximating the pathwidth of outerplanar graphs
Information Processing Letters, 1998Pathwidth is a well-known NP-complete graph metric. We present a technique to approximate the pathwidth of outerplanar graphs. Although a polynomial-time algorithm is already known to determine the pathwidth of outerplanar graphs, this algorithm is not practical.
Rajeev Govindan +2 more
openaire +2 more sources
Online Problems, Pathwidth, and Persistence [PDF]
, 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 ...
Catherine McCartin, Rodney G. Downey
openaire +1 more source
PATHWIDTH AND LAYERED DRAWINGS OF TREES
International Journal of Computational Geometry & Applications, 2004An 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
treewidth pathwidth and cospan decompositions
Electronic Communication of The European Association of Software Science and Technology, 2011OA ...
Blume, Christoph +3 more
openaire +2 more sources
A Linear Algorithm for the Pathwidth of Trees
1990The 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 +2 more sources
Pathwidth of Planar and Line Graphs
Graphs and Combinatorics, 2003We prove that for every 2-connected planar graph the pathwidth of its geometric dual is less than the pathwidth of its line graph. This implies that pathwidth(H)≤ pathwidth(H *)+1 for every planar triangulation H and leads us to a conjecture that pathwidth(G)≤pathwidth(G *)+1 for every 2-connected graph G.
openaire +2 more sources
Submodular Minimization via Pathwidth
2012In this paper, we present a submodular minimization algorithm based on a new relationship between minimizers of a submodular set function and pathwidth defined on submodular set functions. Given a submodular set function f on a finite set V with n ≥2 elements and an ordered pair s ,t ∈V , let λ s ,t denote the minimum f (X ) over all sets X with s ∈X ...
openaire +2 more sources