Research Article
Constrained Routing Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 81 - Issue 7 |
| Published: November 2013 |
| Authors: Pawan Kumar Patel, Rohit Kumar, Nikita Gulati |
10.5120/14023-1676
|
Pawan Kumar Patel, Rohit Kumar, Nikita Gulati . Constrained Routing Problem. International Journal of Computer Applications. 81, 7 (November 2013), 15-17. DOI=10.5120/14023-1676
@article{ 10.5120/14023-1676,
author = { Pawan Kumar Patel,Rohit Kumar,Nikita Gulati },
title = { Constrained Routing Problem },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 81 },
number = { 7 },
pages = { 15-17 },
doi = { 10.5120/14023-1676 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Pawan Kumar Patel
%A Rohit Kumar
%A Nikita Gulati
%T Constrained Routing Problem%T
%J International Journal of Computer Applications
%V 81
%N 7
%P 15-17
%R 10.5120/14023-1676
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In this paper, we have worked on a problem in the domain of graph theory and geometry . Objective of our problem is to find out the shortest path with forbidden pairs in a graphs. Given a graph G=(V, E) and set of pairs P={ai, bi|ai ? V? bi ? V}, we have to find out the shortest path between two given vertices s and t, s. t. ai bi both do not occur on the path for any i. We reduce SAT to this problem and thus claim that this problem is NP-hard.
References
- P. Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the 40th ACM Symposium on the Theory of Computing, pages 245{254, New York, NY, USA, 2008. ACM.
- Y. Zhao, X. Deng, C. H. Lee and H. Zhu, (2 + f(n))-SAT and its properties, Discrete Applied Mathematics 136 (2004), 3–11
- S. Aaronson. Is P versus NP formally independent? Bulletin of the European Association for Theoretical Computer Science, 81, Oct. 2003.
- R. Impagliazzo, R. Paturi, and F. Zane, Which Problems Have Strongly Exponential Complexity?, Journal of Computer and System Sciences 63-4, (2001), pp. 512-530.
- J. Gramm, and R. Niedermeier, Faster exact solutions for Max-2-Sat, in Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science 1767, (2000), pp. 174-186.
- B. Borchers and J. Furman, A two-phase exact algorithm for Max-Sat and weighted Max-Sat problems, J. Combinatorial Optimization 2, (1999), pp. 465-474.
- T. Asano, and D. P. Williamson, Improved Approximation Algorithms for Max-Sat, in Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), (2000),
- N. Bansal and V. Raman, Upper bounds for Max-Sat further improved, in Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 1741, (1999), pp. 247-258.
- Battiti and M. Protasi, Reactive research, a history base heuristic for Max-Sat, J. Exper. Algorithmics 2, No. 2, (1997).
Index Terms
Keywords