Wie heißt dieses Problem mit gerichteten Graphen?

16

Nehmen Sie einen gerichteten Graphen bei dem die Kanten mit einer natürlichen Zahl verziert sind. Wir wollen die Menge aller Pfade P zwischen zwei Eckpunkten v 1 und v 2 so, dass jede aufeinanderfolgende Kante im Pfad mit einer natürlichen Zahl verziert wird, die größer ist als die natürliche Zahl, die die vorherige Kante verziert.GPv1v2

Eine Anwendung hierfür wären Bus- oder Zugfahrpläne. Wenn Sie versuchen, die unterschiedlichen Routen zwischen zwei Städten basierend auf Übertragungen zwischen Stationen zu ermitteln. (Sie können keinen zweiten Zug nehmen, der abfahren soll, bevor der erste ankommt.)

Ich habe dies informell einen "geplanten Graphen" genannt. Aber ich weiß nicht, wie das in der Literatur heißt.

Alle Verweise auf diesbezügliche Algorithmen sind ebenfalls von Interesse.

rauben
quelle
mildly related: cstheory.stackexchange.com/questions/5849/…
Artem Kaznatcheev
1
Wenn Sie das Liniendiagramm von und die Kanten von einem Knoten mit niedrigerer Nummer zu einem Knoten mit höherer Nummer ausrichten, erhalten Sie eine DAG G ' . Umgekehrt kann auf diese Weise eine beliebige azyklische Ausrichtung eines beliebigen Liniendiagramms erhalten werden. Daher scheint Ihr Problem im Wesentlichen dem folgenden Problem zu entsprechen: Finden Sie bei einer azyklischen Ausrichtung eines Liniendiagramms alle gerichteten Pfade, die ein bestimmtes Knotenpaar verbinden. Aber ich bin mir nicht sicher, ob die Eigenschaft, ein Liniendiagramm zu sein, hier wirklich hilft ...? GG
Jukka Suomela

Antworten:

14

Soweit ich weiß, wird das Problem manchmal als "nicht abnehmender Pfad" bezeichnet und wurde seit den 50er Jahren untersucht. Siehe zum Beispiel dieses Papier: GJ Minty. Eine Variante des Shortest-Route-Problems, Operations Research, 6 (6): 882–883, 1958.

st

virgi
quelle