Cristiano Bocci

dblp:82/7318 · DBLP profile ↗
← Back
3ranked-venue papers
2as first author
3since 2021 · last 2024
0000-0002-7874-4419ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 2 first-author · 3 since 2021
YearPublicationVenuePosition
2024 A new temporal interpretation of cluster editing
abstract
The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a natural interpretation of this problem in temporal graphs, whose edge sets change over time. This problem is NP-complete even when restricted to temporal graphs whose underlying graph is a path, but we obtain two polynomial-time algorithms for restricted cases. In the static setting, it is well-known that a graph is a disjoint union of cliques if and only if it contains no induced copy of P3; we demonstrate that no general characterisation involving sets of at most four vertices can exist in the temporal setting, but obtain a complete characterisation involving forbidden configurations on at most five vertices. This characterisation gives rise to an FPT algorithm parameterised simultaneously by the permitted number of modifications and the lifetime of the temporal graph.
Cristiano Bocci, Chiara Capresi, Kitty Meeks, John Sylvester 0001
J. Comput. Syst. Sci.1
2022 A New Temporal Interpretation of Cluster Editing
Cristiano Bocci, Chiara Capresi, Kitty Meeks, John Sylvester 0001
IWOCA1
2022 Catalecticant intersections and confinement of decompositions of forms
Elena Angelini, Cristiano Bocci, Luca Chiantini
J. Symb. Comput.2