Biblioteca Digital do Instituto Politécnico de Bragança   Instituto Politécnico de Bragança

Biblioteca Digital do IPB >
Escola Superior de Tecnologia e Gestão >
Informática e Comunicações >
IC - Artigos em Revistas Indexados ao ISI/Scopus >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10198/4995

Título: An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs
Autor: Gomes, Teresa
Craveirinha, José
Jorge, Luísa
Palavras-chave: OR in telecommunications
Paths with minimal cost sum
Dual arc costs
Disjoint paths
Issue Date: 2009
Editora: Elsevier
Citação: Gomes, Teresa; Craveirinha, José; Jorge, Luísa (2009) - An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs. Computers & Operations Research. ISSN 0305-0548. 36:5, p.1670-1682
Relatório da Série N.º: 5;
Resumo: Routing optimisation in some types of networks requires the calculation of the minimal cost pair of disjoint paths such that the cost functions associated with the arcs in the two paths are different. An exact algorithm for solving this NP-complete problem is proposed, based on a condition which guarantees that the optimal path pair cost has been obtained. This optimality condition is based on the calculation of upper and lower bounds on the optimal cost. A formal proof of the correctness of the algorithm is described. Extensive experimentation is presented to show the effectiveness of the algorithm, including a comparison with an integer linear programming formulation.
Arbitragem científica: yes
URI: http://hdl.handle.net/10198/4995
ISSN: 0305-0548
Appears in Collections:IC - Artigos em Revistas Indexados ao ISI/Scopus

Files in This Item:

File Description SizeFormat
COR09-gomes2008minimalcostpair.pdf631,99 kBAdobe PDFView/Open
Restrict Access. You can request a copy!
COR09-gomes2008minimalcostpair - resumo.pdf99,75 kBAdobe PDFView/Open

Please give feedback about this item
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 


© Instituto Politécnico de Bragança - Biblioteca Digital - Feedback - Statistics
Promotores do RCAAP   Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência PO Sociedade do Conhecimento (POSC) Portal oficial da União Europeia