Algorithms for Finding Diameter Cycles of Biconnected Graphs

In this paper, we first coin a new graph theoretic problem called the diameter cycle problem with numerous applications. A longest cycle in a graph G = (V, E) is referred to as a diameter cycle of G iff the distance in G of every vertex on the cycle to the rest of the on-cycle vertices is maximal. W...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Mehmet Hakan Karaata
Formato:	article
Lenguaje:	EN
Publicado:	University of Zagreb Faculty of Electrical Engineering and Computing 2020
Materias:	biconnected graphs diameter cycle fundamental cycles graph algorithms Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e4ed12fe63cb462f966846a5af76529b
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e4ed12fe63cb462f966846a5af76529b
record_format	dspace
spelling	oai:doaj.org-article:e4ed12fe63cb462f966846a5af76529b2021-12-02T19:42:40ZAlgorithms for Finding Diameter Cycles of Biconnected Graphs1330-11361846-3908https://doaj.org/article/e4ed12fe63cb462f966846a5af76529b2020-01-01T00:00:00Zhttps://hrcak.srce.hr/file/384987https://doaj.org/toc/1330-1136https://doaj.org/toc/1846-3908In this paper, we first coin a new graph theoretic problem called the diameter cycle problem with numerous applications. A longest cycle in a graph G = (V, E) is referred to as a diameter cycle of G iff the distance in G of every vertex on the cycle to the rest of the on-cycle vertices is maximal. We then present two algorithms for finding a diameter cycle of a biconnected graph. The first algorithm is an abstract intuitive algorithm that utilizes a brute-force mechanism for expanding an initial cycle by repeatedly replacing paths on the cycle with longer paths. The second algorithm is a concrete algorithm that uses fundamental cycles in the expansion process and has the time and space complexity of O(n^6) and O(n^2), respectively. To the best of our knowledge, this problem was neither defined nor addressed in the literature. The diameter cycle problem distinguishes itself from other cycle finding problems by identifying cycles that are maximally long while maximizing the distances between vertices in the cycle. Existing cycle finding algorithms such as fundamental and longest cycle algorithms do not discover cycles where the distances between vertices are maximized while also maximizing the length of the cycle.Mehmet Hakan KaraataUniversity of Zagreb Faculty of Electrical Engineering and Computingarticlebiconnected graphsdiameter cyclefundamental cyclesgraph algorithmsElectronic computers. Computer scienceQA75.5-76.95ENJournal of Computing and Information Technology, Vol 28, Iss 4, Pp 225-240 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	biconnected graphs diameter cycle fundamental cycles graph algorithms Electronic computers. Computer science QA75.5-76.95
spellingShingle	biconnected graphs diameter cycle fundamental cycles graph algorithms Electronic computers. Computer science QA75.5-76.95 Mehmet Hakan Karaata Algorithms for Finding Diameter Cycles of Biconnected Graphs
description	In this paper, we first coin a new graph theoretic problem called the diameter cycle problem with numerous applications. A longest cycle in a graph G = (V, E) is referred to as a diameter cycle of G iff the distance in G of every vertex on the cycle to the rest of the on-cycle vertices is maximal. We then present two algorithms for finding a diameter cycle of a biconnected graph. The first algorithm is an abstract intuitive algorithm that utilizes a brute-force mechanism for expanding an initial cycle by repeatedly replacing paths on the cycle with longer paths. The second algorithm is a concrete algorithm that uses fundamental cycles in the expansion process and has the time and space complexity of O(n^6) and O(n^2), respectively. To the best of our knowledge, this problem was neither defined nor addressed in the literature. The diameter cycle problem distinguishes itself from other cycle finding problems by identifying cycles that are maximally long while maximizing the distances between vertices in the cycle. Existing cycle finding algorithms such as fundamental and longest cycle algorithms do not discover cycles where the distances between vertices are maximized while also maximizing the length of the cycle.
format	article
author	Mehmet Hakan Karaata
author_facet	Mehmet Hakan Karaata
author_sort	Mehmet Hakan Karaata
title	Algorithms for Finding Diameter Cycles of Biconnected Graphs
title_short	Algorithms for Finding Diameter Cycles of Biconnected Graphs
title_full	Algorithms for Finding Diameter Cycles of Biconnected Graphs
title_fullStr	Algorithms for Finding Diameter Cycles of Biconnected Graphs
title_full_unstemmed	Algorithms for Finding Diameter Cycles of Biconnected Graphs
title_sort	algorithms for finding diameter cycles of biconnected graphs
publisher	University of Zagreb Faculty of Electrical Engineering and Computing
publishDate	2020
url	https://doaj.org/article/e4ed12fe63cb462f966846a5af76529b
work_keys_str_mv	AT mehmethakankaraata algorithmsforfindingdiametercyclesofbiconnectedgraphs
_version_	1718376116286128128

Algorithms for Finding Diameter Cycles of Biconnected Graphs

Ejemplares similares