Parameterized aspects of triangle enumeration
From MaRDI portal
Publication:5915757
DOI10.1007/978-3-662-55751-8_9zbMATH Open1495.68162arXiv1702.06548OpenAlexW3135299686WikidataQ128295159 ScholiaQ128295159MaRDI QIDQ5915757
Author name not available (Why is that?)
Publication date: 22 November 2017
Published in: (Search for Journal in Brave)
Abstract: The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, "subcubic" parameterized solving algorithms) as well as negative results (presumable uselessness in terms of "faster" parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts.
Full work available at URL: https://arxiv.org/abs/1702.06548
No records found.
No records found.
This page was built for publication: Parameterized aspects of triangle enumeration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5915757)
