Elenco di complessità del problema del postino cinese

[ad_1]

Questo è un elenco di complessità computazionali per diversi problemi di instradamento dell’arco.

Complessità del problema del postino cinese (CP).[edit]

Guarda anche[edit]

Riferimenti[edit]

  1. ^ un b c Edmonds, Jack; Johnson, Ellis L. (1973). “Abbinamento, tournée di Eulero e il postino cinese”. Programmazione matematica. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610.
  2. ^ Yaxiong, Lin; Yongchang, Zhao (gennaio 1988). “Un nuovo algoritmo per il problema del postino cinese diretto”. Computer e ricerca operativa. 15 (6): 577–584. doi:10.1016/0305-0548(88)90053-6. ISSN 0305-0548.
  3. ^ Papadimitriou, Christos H. (luglio 1976). “Sulla complessità del edge traversing”. Giornale dell’ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411.
  4. ^ un b Guan, Meigu (settembre 1984). “Sul ventoso problema del postino”. Matematica applicata discreta. 9 (1): 41–46. doi:10.1016/0166-218x(84)90089-1. ISSN 0166-218X.
  5. ^ Vinci, Zaw (maggio 1989). “Sul problema del postino ventoso sui grafici euleriani”. Programmazione matematica. 44 (1–3): 97–112. doi:10.1007/bf01587080. ISSN 0025-5610.
  6. ^ Dror, Moshe; poppa, Helman; Trudeau, Pierre (1987). “Tour del postino su un grafico con relazione di precedenza sugli archi”. Reti. 17 (3): 283–294. doi:10.1002/net.3230170304. ISSN 0028-3045.
  7. ^ “12° congresso mondiale dell’informatica — congresso IFIP’92”. Computer nell’industria. 20 (1): 124–126. gennaio 1992. doi:10.1016/0166-3615(92)90137-c. ISSN 0166-3615.
  8. ^ Thomassen, Carsten (giugno 1997). “Sulla complessità di trovare una copertura ciclo minima di un grafico”. Giornale SIAM sull’informatica. 26 (3): 675–677. doi:10.1137/s0097539794267255. ISSN 0097-5397.
  9. ^ Frederickson, Greg N.; Hecht, Matteo S.; Kim, Chul E. (maggio 1978). “Algoritmi di approssimazione per alcuni problemi di instradamento”. Giornale SIAM sull’informatica. 7 (2): 178–193. doi:10.1137/0207017. ISSN 0097-5397.
  10. ^ Raghavachari, Balaji; Veerasamy, Jeyakesavan (gennaio 1999). “Un algoritmo di approssimazione 3/2 per il problema del postino misto”. SIAM Journal sulla matematica discreta. 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801.
  11. ^ Raghavachari, Balaji; Veerasamy, Jeyakesavan (gennaio 1999). “Un algoritmo di approssimazione 3/2 per il problema del postino misto”. SIAM Journal sulla matematica discreta. 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801.
  12. ^ Frederickson, Greg N.; Hecht, Matteo S.; Kim, Chul E. (maggio 1978). “Algoritmi di approssimazione per alcuni problemi di instradamento”. Giornale SIAM sull’informatica. 7 (2): 178–193. doi:10.1137/0207017. ISSN 0097-5397.
  13. ^ un b Gutin, Gregorio; Jones, Marco; Sheng, Bin (2014), “Complessità parametrizzata del problema del postino cinese k-Arc”, Algoritmi – SEC 2014Berlino, Heidelberg: Springer Berlin Heidelberg, pp. 530–541, ISBN 978-3-662-44776-5recuperato 09-05-2022
  14. ^ Fernandes, Cristina G.; Lee, Orlando; Wakabayashi, Yoshiko (gennaio 2009). “Copertura minima del ciclo e problemi del postino cinese su grafi misti con larghezza dell’albero limitata”. Matematica applicata discreta. 157 (2): 272–279. doi:10.1016/j.dam.2007.10.032. ISSN 0166-218X.
  15. ^ Corberán, Angelo (2015). Instradamento ad arco: problemi, metodi e applicazioni. ISBN 978-1-61197-366-2.


[ad_2]
Source link

Rispondi

%d blogger hanno fatto clic su Mi Piace per questo: