Results 141 to 147 of about 2,730 (147)

Herding in groundfish and effective pathwidth of trawls

Fisheries Research, 1995
Abstract The swept area method requires quantitative information on the effective pathwidth W eff of a trawl to estimate absolute densities of groundfish. Herding of some groundfish by the bridles, sweeps and doors of a trawl will extend W eff beyond that of the net proper and limits applicability of that method.
Yongshun Xiao, David C. Ramm
openaire   +2 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   +2 more sources

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   +4 more sources

Pathwidth of Planar and Line Graphs

Graphs and Combinatorics, 2003
We 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

Better algorithms for the pathwidth and treewidth of graphs

1991
In this paper we give, for all constants k, explicit O(n log2n) algorithms, that given a graph G = (V,E), decide whether the treewidth (or pathwidth) of G is at most k, and if so, find a tree-decomposition or (path-decomposition) of G with treewidth (or pathwidth) at most k.
Ton Kloks, Hans L. Bodlaender
openaire   +2 more sources

Submodular Minimization via Pathwidth

2012
In 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

Pathwidth of pathwidth-bounded graphs

2006
openaire   +1 more source