Results 81 to 90 of about 98 (93)
On the treewidth and pathwidth of permutation graphs
, 1992 Kloks, A.J.J., Bodlaender, H.L.
openaire +2 more sources
Some of the next articles are maybe not open access.
Related searches:
Related searches:
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
Directed Pathwidth and Palletizers
2015In 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 +2 more
openaire +1 more source
Pathwidth of Planar and Line Graphs
Graphs and Combinatorics, 2003The 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
Nondeterministic Graph Searching: From Pathwidth to Treewidth
Algorithmica, 2005zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Fomin, Fedor V. +2 more
openaire +4 more sources
Near Unanimity Constraints Have Bounded Pathwidth Duality
2012 27th Annual IEEE Symposium on Logic in Computer Science, 2012We show that if a finite relational structure has a near unanimity polymorphism, then the constraint satisfaction problem with that structure as its fixed template has bounded pathwidth duality, putting the problem in nondeterministic logspace. This generalizes the analogous result of Dalmau and Krokhin for majority polymorphisms and lends further ...
Barto, Libor +2 more
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 +1 more source
Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
Journal of Algorithms, 1995Summary: Various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are not more than \(
Bodlaender, H. L. +3 more
openaire +3 more sources
Online Problems, Pathwidth, and Persistence
2004We 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