Premium
The 2‐path network problem
Author(s) -
Dahl Geir,
Johannessen Bjarne
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20003
Subject(s) - polytope , integer programming , path (computing) , combinatorics , mathematics , set (abstract data type) , node (physics) , graph , enhanced data rates for gsm evolution , longest path problem , computer science , mathematical optimization , discrete mathematics , shortest path problem , artificial intelligence , structural engineering , engineering , programming language
Abstract Given a graph with nonnegative edge weights and a set D of node pairs, the 2‐ path network problem requires a minimum weight set of edges such that the induced subgraph contains a path with one or two edges connecting each pair in D . The problem is NP ‐hard. We present two integer programming models for the problem and study properties of associated polytopes, including cutting planes. Two approximation algorithms are suggested and analyzed. Some computational experience is reported. © 2004 Wiley Periodicals, Inc.