Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
On the Recognition of k-Equistable Graphs
verfasst von : Vadim E. Levit, Martin Milanič, David Tankus
Erschienen in: Graph-Theoretic Concepts in Computer Science
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
A graph
G
= (
V
,
E
) is called
equistable
if there exist a positive integer
t
and a weight function
$w:V \longrightarrow \mathbb{N}$
such that
S
⊆
V
is a maximal stable set of
G
if and only if
w
(
S
) =
t
. The function
w
, if exists, is called an
equistable function
of
G
. No combinatorial characterization of equistable graphs is known, and the complexity status of recognizing equistable graphs is open. It is not even known whether recognizing equistable graphs is in
NP
.
Let
k
be a positive integer. An equistable graph
G
= (
V
,
E
) is said to be
k-equistable
if it admits an equistable function which is bounded by
k
. For every constant
k
, we present a polynomial time algorithm which decides whether an input graph is
k
-equistable.