CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Constrained Routing Problem

by Pawan Kumar Patel, Rohit Kumar, Nikita Gulati
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 81 - Number 7
Year of Publication: 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 },
issue_date = { November 2013 },
volume = { 81 },
number = { 7 },
month = { November },
year = { 2013 },
issn = { 0975-8887 },
pages = { 15-17 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume81/number7/14023-1676/ },
doi = { 10.5120/14023-1676 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:55:27.085285+05:30
%A Pawan Kumar Patel
%A Rohit Kumar
%A Nikita Gulati
%T Constrained Routing Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 81
%N 7
%P 15-17
%D 2013
%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
  1. 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.
  2. Y. Zhao, X. Deng, C. H. Lee and H. Zhu, (2 + f(n))-SAT and its properties, Discrete Applied Mathematics 136 (2004), 3–11
  3. S. Aaronson. Is P versus NP formally independent? Bulletin of the European Association for Theoretical Computer Science, 81, Oct. 2003.
  4. 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.
  5. 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.
  6. 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.
  7. 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),
  8. 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.
  9. Battiti and M. Protasi, Reactive research, a history base heuristic for Max-Sat, J. Exper. Algorithmics 2, No. 2, (1997).
Index Terms

Computer Science
Information Sciences

Keywords

Shortest path with forbidden pairs NP-hard Computational geometry Graph theory.

Powered by PhDFocusTM