2026-07-22T16:55:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12782 2024-03-06T10:49:10Z ddc:004 open_access

Speeding up Networks Mining via Neighborhood Diversity Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Parameterized Complexity Neighborhood Diversity Maximum Matching Triangle Counting Girth Global minimum vertex cut 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gennaro Cordasco and Luisa Gargano and Adele A. Rescigno 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.21 urn:nbn:de:0030-drops-127823 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.21 eng https://creativecommons.org/licenses/by/3.0/legalcode