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.

Speeding up networks mining via neighborhood diversity

Cordasco G.;
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11591/435742
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact