2012 | OriginalPaper | Buchkapitel
Packing Euler graphs with traces
verfasst von : Peter Recht, Eva-Maria Sprengel
Erschienen in: Operations Research Proceedings 2011
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
For a graph
G
= (
V,E
) and a vertex
v ∈ V
, let
T
(
v
) be a
local trace
at
v
, i.e.
T
(
v
) is an Eulerian subgraph of
G
such that every walk
W
(
v
), with start vertex
v
can be extended to an Eulerian tour in
T
(
v
). In general, local traces are not unique. We prove that if
G
is Eulerian every maximum edge-disjoint cycle packing
Z*
of
G
induces maximum local traces
T
(
v
) at
v
for every
v ∈ V
. In the opposite, if the total size
$$ \sum $$V∈E
|(
T
(
v
)|
|
is minimal then the set of related edge-disjoint cycles in
G
must be maximum.