Advertisement
Published in:
2012 | OriginalPaper | Chapter
Submodular Minimization via Pathwidth
Author : Hiroshi Nagamochi
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
⊆
V
− {
t
}. The pathwidth Λ(
σ
) of a sequence
σ
of all
n
elements in
V
is defined to be the maximum
f
(
V
(
σ
′)) over all nonempty and proper prefixes
σ
′ of
σ
, where
V
(
σ
′) denotes the set of elements occurred in
σ
′. The pathwidth Λ
s
,
t
of
f
from
s
to
t
is defined to be the minimum pathwidth Λ(
σ
) over all sequences
σ
of
V
which start with element
s
and end up with
t
. Given a real
k
≥
f
({
s
}), our algorithm checks whether Λ
s
,
t
≤
k
or not and computes
λ
s
,
t
(when Λ
s
,
t
≤
k
) in
O
(
n
Δ(
k
) + 1
) oracle-time, where Δ(
k
) is the number of distinct values of
f
(
X
) with
f
(
X
) ≤
k
overall sets
X
with
s
∈
X
⊆
V
− {
t
}.