Geodesic
On the Isometric Path Partition Problem
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1077-1089

Voir la notice de l'article provenant de la source Library of Science

The isometric path cover (partition) problem of a graph consists of finding a minimum set of isometric paths which cover (partition) the vertex set of the graph. The isometric path cover (partition) number of a graph is the cardinality of a minimum isometric path cover (partition). We prove that the isometric path partition problem and the isometric k-path partition problem for k 3 are NP-complete on general graphs. Fisher and Fitzpatrick in [The isometric number of a graph, J. Combin. Math. Combin. Comput. 38 (2001) 97–110] have shown that the isometric path cover number of the (r × r)-dimensional grid is ⌈2r/3 ⌉. We show that the isometric path cover (partition) number of the (r × s)-dimensional grid is s when r s(s − 1). We establish that the isometric path cover (partition) number of the (r × r)-dimensional torus is r when r is even and is either r or r + 1 when r is odd. Then, we demonstrate that the isometric path cover (partition) number of an r-dimensional Benes network is 2r. In addition, we provide partial solutions for the isometric path cover (partition) problems for cylinder and multi-dimensional grids. We apply two di erent techniques to achieve these results.
Keywords: path cover problem, isometric path partition problem, isometric path cover problem, multi-dimensional grids, cylinder, torus 
Manuel, Paul. On the Isometric Path Partition Problem. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1077-1089. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a13/
@article{DMGT_2021_41_4_a13,
     author = {Manuel, Paul},
     title = {On the {Isometric} {Path} {Partition} {Problem}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1077--1089},
     year = {2021},
     volume = {41},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a13/}
}
TY  - JOUR
AU  - Manuel, Paul
TI  - On the Isometric Path Partition Problem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1077
EP  - 1089
VL  - 41
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a13/
LA  - en
ID  - DMGT_2021_41_4_a13
ER  - 
%0 Journal Article
%A Manuel, Paul
%T On the Isometric Path Partition Problem
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1077-1089
%V 41
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a13/
%G en
%F DMGT_2021_41_4_a13

[1] A. Aggarwal, J.M. Kleinberg and D.P. Williamson, Node-disjoint paths on the mesh and a new trade-o in VLSI layout, SIAM J. Comput. 29 (2000) 1321–1333. https://doi.org/10.1137/S0097539796312733

[2] T. Akiba, Y. Iwata and Y. Yoshida, Fast exact shortest-path distance queries on large networks by pruned landmark labeling, in: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, USA, ACM Digital Library (2013) 349–360. https://doi.org/10.1145/2463676.2465315

[3] J.S. Baras and G. Theodorakopoulos, Path problems in networks, Synth. Lect. Commun. Netw. 3 (2010) 1–77. https://doi.org/10.2200/S00245ED1V01Y201001CNT003

[4] G. Chartrand, J. McCanna, N. Sherwani, M. Hossain and J. Hashmi, The induced path number of bipartite graphs, Ars Combin. 37 (1994) 191–208.

[5] J.C.N. Clímaco, J.M.F. Craveirinha and M.M.B. Pascoal, A bicriterion approach for routing problems in multimedia networks, Networks 41 (2003) 206–220. https://doi.org/10.1002/net.10073

[6] J. Cota-Ruiz, P. Rivas-Perea, E. Sifuentes and R. Gonzalez-Landaeta, A recursive shortest path routing algorithm with application for wireless sensor network localization, IEEE Sensors J. 16 (2016) 4631–4637. https://doi.org/10.1109/JSEN.2016.2543680

[7] D.C. Fisher and S.L. Fitzpatrick, The isometric number of a graph, J. Combin. Math. Combin. Comput. 38 (2001) 97–110.

[8] S.L. Fitzpatrick, Aspects of Domination and Dynamic Domination (PhD Thesis, Department of Mathematics, Dalhousie University, Nova Scotia, Canada, 1997).

[9] S.L. Fitzpatrick, The isometric path number of the Cartesian product of paths, Congr. Numer. 137 (1999) 109–119.

[10] S.L. Fitzpatrick, R.J. Nowakowski, D.A. Holton and I. Caines, Covering hypercubes by isometric paths, Discrete Math. 240 (2001) 253–260. https://doi.org/10.1016/S0012-365X(01)00197-2

[11] M. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

[12] M. Gong, G. Li, Z. Wang, L. Ma and D. Tian, An efficient shortest path approach for social networks based on community structure, CAAI Trans. Intelligence Technology 1 (2016) 114–123. https://doi.org/10.1016/j.trit.2016.03.011

[13] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (A K Peters, Ltd., Wellesley, MA, 2008). https://doi.org/10.1201/b10613

[14] M.L. Lamali, N. Fergani, J. Cohen and H. Pouyllau, Path computation in multilayer networks: Complexity and algorithms, IEEE INFOCOM, San Francisco, CA, USA, IEEE Computer Society 26 (2016) 1–9. https://doi.org/10.1109/INFOCOM.2016.7524550

[15] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays Trees, Hypercubes (Morgan Kaufmann Publishers, 1992). https://doi.org/10.1016/B978-1-4832-0772-8.50005-4

[16] P. Manuel, Revisiting path-type covering and partitioning problems, manuscript (2018).

[17] P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj and E. Thomas, Strong edge geodetic problem in networks, Open Math. 15 (2017) 1225–1235. https://doi.org/10.1515/math-2017-0101

[18] P.D. Manuel, M.I. Abd-El-Barr, I. Rajasingh and B. Rajan, An efficient representation of Benes networks and its applications, J. Discrete Algorithms 6 (2008) 11–19. https://doi.org/10.1016/j.jda.2006.08.003

[19] J. Monnot and S. Toulouse, The path partition problem and related problems in bipartite graphs, Oper. Res. Lett. 35 (2007) 677–684. https://doi.org/10.1016/j.orl.2006.12.004

[20] H. Ortega-Arranz, D.R. Llanos and A. Gonzalez-Escribano, The shortest-path problem: Analysis and comparison of methods, Synth. Lect. Theor. Comput. Sci. 1 (2014) 1–87. https://doi.org/10.2200/S00618ED1V01Y201412TCS001

[21] J.-J. Pan and G.J. Chang, Isometric-path numbers of block graphs, Inform. Process. Lett. 93 (2005) 99–102. https://doi.org/10.1016/j.ipl.2004.09.021

[22] J.-J. Pan and G.J. Chang, Isometric path numbers of graphs, Discrete Math. 306 (2006) 2091–2096. https://doi.org/10.1016/j.disc.2006.04.003

[23] S.K. Peer and D.K. Sharma, Finding the shortest path in stochastic networks, Comput. Math. Appl. 53 (2007) 729–740. https://doi.org/10.1016/j.camwa.2007.01.012

[24] M. Pióro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks (Morgan Kaufmann Publishers, 2004). https://doi.org/10.1016/B978-0-12-557189-0.X5000-8

[25] J. Xu, Topological Structure and Analysis of Interconnection Networks (Springer-Verlag, 2001). https://doi.org/10.1007/978-1-4757-3387-7

[26] J. Zhang, W. Luo, L. Yuan and W. Mei, Shortest path algorithm in GIS network analysis based on Cli ord algebra, in: Proc. 2nd International Conference on Future Computer and Communication 1 (2010) 432–436. https://doi.org/10.1109/ICFCC.2010.5497752