Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Linear Layouts in Submodular Systems
verfasst von : Hiroshi Nagamochi
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Linear layout of graphs/digraphs is one of the classical and important optimization problems that have many practical applications. Recently Tamaki proposed an
O
(
mn
k
+ 1
)-time and
O
(
n
k
)-space algorithm for testing whether the pathwidth (or vertex separation) of a given digraph with
n
vertices and
m
edges is at most
k
. In this paper, we show that linear layout of digraphs with an objective function such as cutwidth, minimum linear arrangement, vertex separation (or pathwidth) and sum cut can be formulated as a linear layout problem on a submodular system (
V
,
f
) and then propose a simple framework of search tree algorithms for finding a linear layout (a sequence of
V
) with a bounded width that minimizes a given cost function. According to our framework, we obtain an
O
(
k
m
n
2
k
)-time and
O
(
n
+
m
)-space algorithm for testing whether the pathwidth of a given digraph is at most
k
.