Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Tree Path Labeling of Hypergraphs – A Generalization of the Consecutive Ones Property
verfasst von : N. S. Narayanaswamy, Anju Srinivasan
Erschienen in: Algorithms and Discrete Applied Mathematics
Verlag: Springer International Publishing
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
Given a set system
$\mathcal{F} \subseteq$
(2
U
∖ ∅ ) of a finite set
U
of cardinality
n
and a tree
T
of size
n
, does there exist at least one bijection
φ
:
U
→
V
(
T
) such that for each
$S \in \mathcal{F}$
, the set {
φ
(
x
) |
x
∈
S
} is the vertex set of a path in
T
? Our main result is that the existence of such a bijection from
U
to
V
(
T
) is equivalent to the existence of a function
$\mathcal{l}$
from
$\mathcal{F}$
to the set of all paths in
T
such that for any
three
, not necessarily distinct,
$S_1, S_2, S_3 \in \mathcal{F}$
,
$|S_1 \cap S_2 \cap S_3|=|\mathcal{l}(S_1) \cap \mathcal{l}(S_2) \cap \mathcal{l}(S_3)|$
.
$\mathcal{l}$
is referred to as a
tree path labeling
of
$\mathcal{F}$
.