Apa nama dari jenis grafik yang diarahkan ini?

16

Ambil grafik terarah mana tepinya didekorasi dengan bilangan alami. Kami ingin himpunan semua jalur P antara dua simpul v 1 dan v 2 sedemikian rupa sehingga setiap tepi berurutan di jalur dihiasi dengan bilangan alami yang lebih besar dari bilangan alami yang menghiasi tepi sebelumnya.GPv1v2

Aplikasi untuk ini adalah jadwal bus atau kereta api. Jika Anda mencoba menentukan rute berbeda antara dua kota berdasarkan transfer antar stasiun. (Anda tidak dapat naik kereta kedua yang dijadwalkan berangkat sebelum yang pertama tiba.)

Saya secara informal menyebut ini "grafik terjadwal". Tetapi saya tidak tahu apa nama ini dalam literatur.

Referensi apa pun yang berkaitan dengan algoritma ini juga menarik.

ds.algorithms reference-request graph-algorithms terminology rampok
sumber
sedikit terkait: cstheory.stackexchange.com/questions/5849/…
Artem Kaznatcheev
1
Jika Anda mempertimbangkan grafik garis dan mengorientasikan tepi dari simpul bernomor lebih rendah ke simpul bernomor lebih tinggi, Anda memperoleh DAG G ′ . Sebaliknya, setiap orientasi asiklik dari grafik garis apa pun dapat diperoleh dengan cara ini. Karenanya masalah Anda tampaknya pada dasarnya sama dengan masalah berikut: diberi orientasi asiklik pada grafik garis, temukan semua jalur terarah yang bergabung dengan sepasang node tertentu. Tetapi saya tidak yakin apakah properti menjadi grafik garis benar-benar membantu di sini ...? GG′
Jukka Suomela

Jawaban:

14

Sejauh yang saya tahu, masalahnya kadang-kadang disebut "nondecreasing paths", dan telah dipelajari sejak 50-an. Lihat misalnya makalah ini: GJ Minty. Varian pada Masalah Rute Terpendek, Riset Operasi, 6 (6): 882–883, 1958.

st

virgi
sumber