On the computational complexity of the strong geodetic recognition problem

Open Access

Issue		RAIRO-Oper. Res. Volume 58, Number 5, September-October 2024


Page(s)		3755 - 3770
DOI		https://doi.org/10.1051/ro/2024120
Published online		24 September 2024

B.M. Alom, S. Das and M.S. Islam, Finding the maximum matching in a bipartite graph. DUET J. 1 (2010) 1–4. [Google Scholar]
M. Atici, Computational complexity of geodetic set. Int. J. Comput. Math. 79 (2002) 587-591. [CrossRef] [MathSciNet] [Google Scholar]
M. Atici, On the edge geodetic number of a graph. Int. J. Comput. Math. 80 (2003) 853-861. [CrossRef] [MathSciNet] [Google Scholar]
A. Behtoei, M. Jannesari and B. Taeri, A characterization of block graphs. Discrete Appl. Math. 158 (2010) 219-221. [CrossRef] [MathSciNet] [Google Scholar]
A.A. Bertossi, Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19 (1984) 37-40. [CrossRef] [Google Scholar]
A. Blokhuis and A.E. Brouwer, Geodetic graphs of diameter two, edited by M. Aschbacher, A.M. Cohen and W. M. Kantor. In: Geometries and Groups. Dordrecht, Springer Netherlands (1988) 527-533. [CrossRef] [Google Scholar]
H.L. Bodlaender, S. Thomasse and A. Yeo, Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412 (2011) 4570-4578. [CrossRef] [Google Scholar]
B. Brear, S. Klavžar and A.T. Horvat, On the geodetic number and related metric sets in Cartesian product graphs. Discrete Math. 308 (2008) 5555–5561. [CrossRef] [MathSciNet] [Google Scholar]
L.R. Bueno, L.D. Penso, F. Protti, V.R. Ramos, D. Rautenbach and U.S. Souza, On the hardness of fnding the geodetic number of a subcubic graph. Inf. Process. Lett. 135 (2018) 22–27. [CrossRef] [Google Scholar]
J. Cao, B. Wu and M. Shi, The geodetic number of C_m × C_n. In: International Conference on Management and Service Science (MASS’09) (2009) 1–3. [Google Scholar]
M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms. Springer (2015). [CrossRef] [Google Scholar]
T. Davot, L. Isenmann and J. Thiebaut, On the approximation hardness of geodetic set and its variants. In: Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings 27. Springer (2021) 76–88. [Google Scholar]
J.H.G. de Sousa, Exact algorithms and computational complexity for the strong geodetic set problem, Master’s thesis, Universidade Federal de Minas Gerais (2018). [Google Scholar]
M.C. Dourado, F. Protti, D. Rautenbach and J.L. Szwarcfter, Some remarks on the geodetic number of a graph. Discrete Math. 310 (2010) 832–837. [CrossRef] [MathSciNet] [Google Scholar]
R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer Science & Business Media (2012). [Google Scholar]
R.G. Downey and M.R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer (2013). [CrossRef] [Google Scholar]
T. Ekim and A. Erey, Block decomposition approach to compute a minimum geodetic set. RAIRO:RO 48 (2014) 497–507. [CrossRef] [EDP Sciences] [Google Scholar]
T. Ekim, A. Erey, P. Heggernes, P. van ’t Hof and D. Meister, Computing minimum geodetic sets of proper interval graphs, edited by D. Fern´andez-Baca. In: LATIN 2012: Theoretical Informatics. Berlin, Heidelberg, Springer (2012) 279–290. [CrossRef] [Google Scholar]
M.R. Fellows, L. Jafke, A.I. Kir´aly, F.A. Rosamond and M. Weller, What Is Known About Vertex Cover Kernelization?. Springer International Publishing, Cham (2018) 330–356. [Google Scholar]
S.L. Fitzpatrick, Aspects of domination and dynamic domination, Ph.D. thesis, Dalhousie University (1997). [Google Scholar]
V. Gledel and V. Iršič, Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes. Bull. Malays. Math. Sci. Soc. 43 (2020) 2757–2767. [CrossRef] [MathSciNet] [Google Scholar]
V. Gledel, V. Iršič and S. Klavžar, Strong geodetic cores and Cartesian product graphs. Appl. Math. Comput. 363 (2019) 124609. [MathSciNet] [Google Scholar]
F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph. Math. Comput. Model. 17 (1993) 89–95. [CrossRef] [Google Scholar]
C. Hernando, T. Jiang, M. Mora, I.M. Pelayo and C. Seara, On the Steiner, geodetic and hull numbers of graphs. Discrete Math. 293 (2005) 139–154. [CrossRef] [MathSciNet] [Google Scholar]
J.-T. Hung, L.-D. Tong and H.-T. Wang, The hull and geodetic numbers of orientations of graphs. Discrete Math. 309 (2009) 2134–2139. [CrossRef] [MathSciNet] [Google Scholar]
V. Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specifed diameter. Graphs Combin. 34 (2018) 443–456. [CrossRef] [MathSciNet] [Google Scholar]
V. Iršič and S. Klavžar, Strong geodetic problem on Cartesian products of graphs. RAIRO:RO 52 (2018) 205–216. [CrossRef] [EDP Sciences] [Google Scholar]
V. Iršič and M. Konvalinka, Strong geodetic problem on complete multipartite graphs. Ars Math. Contemp. 17 (2019) 481–491. [CrossRef] [MathSciNet] [Google Scholar]
R.M. Karp, Reducibility among Combinatorial Problems. Springer US, Boston, MA (1972) 85–103. [Google Scholar]
S. Klavžar and P. Manuel, Strong geodetic problem in grid-like architectures. Bull. Malays. Math. Sci. Soc. 41 (2018) 1671–1680. [CrossRef] [MathSciNet] [Google Scholar]
P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj and E. Thomas, Strong geodetic problem in networks. Discuss. Math. Graph Theory 40 (2020) 307–321. [CrossRef] [MathSciNet] [Google Scholar]
L. Nebesky`, New proof of a characterization of geodetic graphs. Czech. Math. J. 52 (2002) 33–39. [CrossRef] [Google Scholar]
V.T. Paschos, A survey of approximately optimal solutions to some covering and packing problems. ACM Comput. Surv. 29 (1997) 171–209. [CrossRef] [Google Scholar]
J. Plesn´ık, A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs. J. Combin. Theory Ser. B 36 (1984) 284–297. [CrossRef] [MathSciNet] [Google Scholar]
A. Santhakumaran, P. Titus and J. John, The upper connected geodetic number and forcing connected geodetic number of a graph. Discrete Appl. Math. 157 (2009) 1571–1580. [CrossRef] [MathSciNet] [Google Scholar]
T.J. Schaefer, The complexity of satisfability problems. In: Proceedings of the tenth annual ACM symposium on Theory of computing. ACM (1978) 216–226. [Google Scholar]
Z. Wang, Y. Mao, H. Ge and C. Magnant, Strong geodetic number of graphs and connectivity. Bull. Malays. Math. Sci. Soc. (2019) 1–11. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.