DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2021.21

Speeding up Networks Mining via Neighborhood Diversity

Authors: Gennaro Cordasco, Luisa Gargano, and Adele A. Rescigno

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract

Parameterized complexity was classically used to efficiently solve NP-hard problems for small values of a fixed parameter. Then it has also been used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd) for several graph theoretic problems in P (e.g., Maximum Matching, Triangle counting and listing, Girth and Global minimum vertex cut). Such problems are known to admit algorithms parameterized by modular-width (mw) and consequently - being the nd a "special case" of mw - by nd. However, the proposed novel algorithms allow to improve the computational complexity from a time O(f(mw)⋅ n +m) - where n and m denote, respectively, the number of vertices and edges in the input graph - which is multiplicative in n to a time O(g(nd)+n +m) which is additive only in the size of the input.

Cite as

Gennaro Cordasco, Luisa Gargano, and Adele A. Rescigno. Speeding up Networks Mining via Neighborhood Diversity. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cordasco_et_al:LIPIcs.FUN.2021.21,
  author =	{Cordasco, Gennaro and Gargano, Luisa and Rescigno, Adele A.},
  title =	{{Speeding up Networks Mining via Neighborhood Diversity}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.21},
  URN =		{urn:nbn:de:0030-drops-127823},
  doi =		{10.4230/LIPIcs.FUN.2021.21},
  annote =	{Keywords: Parameterized Complexity, Neighborhood Diversity, Maximum Matching, Triangle Counting, Girth, Global minimum vertex cut}
}

Search Results

Documents authored by Cordasco, Gennaro

Speeding up Networks Mining via Neighborhood Diversity

Abstract

Cite as

Thanks for your feedback!

Could not send message