Qual é o nome desse tipo de problema de gráfico direcionado?

16

Faça um gráfico direcionado onde as bordas são decoradas com um número natural. Queremos o conjunto de todos os caminhos P entre dois vértices v 1 e v 2, de modo que cada aresta sucessiva no caminho seja decorada com um número natural que seja maior que o número natural que decora a aresta anterior.GPv1 1v2

Uma aplicação para isso seria horários de ônibus ou trem. Se você estiver tentando determinar as diferentes rotas entre duas cidades com base nas transferências entre estações. (Você não pode pegar um segundo trem programado para partir antes que o primeiro chegue.)

Eu informalmente chamo isso de "gráfico programado". Mas não sei qual é o nome disso na literatura.

Qualquer referência a algoritmos relacionados a isso também é interessante.

ds.algorithms reference-request graph-algorithms terminology Roubar
fonte
levemente relacionado: cstheory.stackexchange.com/questions/5849/…
Artem Kaznatcheev
11
Se você considerar o gráfico de linhas de e orientar as arestas de um nó de número inferior para um nó de número superior, você obtém um DAG G ' . Por outro lado, qualquer orientação acíclica de qualquer gráfico de linhas pode ser obtida dessa maneira. Portanto, seu problema parece ser essencialmente igual ao seguinte problema: dada uma orientação acíclica de um gráfico de linhas, encontre todos os caminhos direcionados que se juntam a um determinado par de nós. Mas não tenho certeza se a propriedade de ser um gráfico de linha realmente ajuda aqui ...? GG′
Jukka Suomela

Respostas:

14

Até onde eu sei, o problema às vezes é chamado de "caminhos não decrescentes" e foi estudado desde os anos 50. Veja, por exemplo, este artigo: GJ Minty. Uma variante do problema da rota mais curta, Operations Research, 6 (6): 882–883, 1958.

st

virgi
fonte