Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time [Formula: see text] . The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-...

Descripción completa

Detalles Bibliográficos
Autores principales: Sankowski, Piotr, Węgrzycki, Karol
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2018
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6647240/
https://www.ncbi.nlm.nih.gov/pubmed/31396014
http://dx.doi.org/10.1007/s00224-018-9894-x
_version_ 1783437687868358656
author Sankowski, Piotr
Węgrzycki, Karol
author_facet Sankowski, Piotr
Węgrzycki, Karol
author_sort Sankowski, Piotr
collection PubMed
description Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time [Formula: see text] . The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-vector multiplication. It allows us to solve the All-Nodes Shortest Cycles, All-Pairs All Walks problems efficiently and also give some improvement upon distance queries in unweighted graphs.
format Online
Article
Text
id pubmed-6647240
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Springer US
record_format MEDLINE/PubMed
spelling pubmed-66472402019-08-06 Improved Distance Queries and Cycle Counting by Frobenius Normal Form Sankowski, Piotr Węgrzycki, Karol Theory Comput Syst Article Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time [Formula: see text] . The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-vector multiplication. It allows us to solve the All-Nodes Shortest Cycles, All-Pairs All Walks problems efficiently and also give some improvement upon distance queries in unweighted graphs. Springer US 2018-11-21 2019 /pmc/articles/PMC6647240/ /pubmed/31396014 http://dx.doi.org/10.1007/s00224-018-9894-x Text en © The Author(s) 2018 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
spellingShingle Article
Sankowski, Piotr
Węgrzycki, Karol
Improved Distance Queries and Cycle Counting by Frobenius Normal Form
title Improved Distance Queries and Cycle Counting by Frobenius Normal Form
title_full Improved Distance Queries and Cycle Counting by Frobenius Normal Form
title_fullStr Improved Distance Queries and Cycle Counting by Frobenius Normal Form
title_full_unstemmed Improved Distance Queries and Cycle Counting by Frobenius Normal Form
title_short Improved Distance Queries and Cycle Counting by Frobenius Normal Form
title_sort improved distance queries and cycle counting by frobenius normal form
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6647240/
https://www.ncbi.nlm.nih.gov/pubmed/31396014
http://dx.doi.org/10.1007/s00224-018-9894-x
work_keys_str_mv AT sankowskipiotr improveddistancequeriesandcyclecountingbyfrobeniusnormalform
AT wegrzyckikarol improveddistancequeriesandcyclecountingbyfrobeniusnormalform

Ejemplares similares