Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Aida Aminian

dblp:397/9384 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2025
0009-0006-3117-5518ORCID · reported

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

Theory of computation · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Approximation and online algorithms · 50% Graph algorithms and graph theory · 25% Computational complexity · 25%

Topics — the 3 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Approximation and online algorithms
approximation algorithms
0.912025
On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs · ICALP 2025
Approximation and online algorithms › approximation algorithms
constant-factor approximation
0.912025
On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs · ICALP 2025
Graph algorithms and graph theory › network analysis › network diffusion
telephone broadcast
0.912025
On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs · ICALP 2025
YearPublicationVenuePosition
2025 On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs
abstract
In Telephone Broadcasting, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of its uninformed neighbors. For general graphs of n vertices, the problem is NP-complete, and the best existing algorithm has an approximation factor of 𝒪(log n/ log log n). The existence of a constant factor approximation for the general graphs is still unknown. In this paper, we study the problem in two simple families of sparse graphs, namely, cacti and graphs of bounded pathwidth. There have been several efforts to understand the complexity of the problem in cactus graphs, mostly establishing the presence of polynomial-time solutions for restricted families of cactus graphs (e.g., [Čevnik and Žerovnik, 2017; Ehresmann, 2021; Harutyunyan et al., 2009; Harutyunyan and Maraachlian, 2007; Harutyunyan and Maraachlian, 2008; Harutyunyan et al., 2023]). Despite these efforts, the complexity of the problem in arbitrary cactus graphs remained open. We settle this question by establishing the NP-completeness of telephone broadcasting in cactus graphs. For that, we show the problem is NP-complete in a simple subfamily of cactus graphs, which we call snowflake graphs. These graphs are not only cacti but also have pathwidth 2. These results establish that, despite being polynomial-time solvable in trees, the problem becomes NP-complete in very simple extensions of trees. On the positive side, we present constant-factor approximation algorithms for the studied families of graphs, namely, an algorithm with an approximation factor of 2 for cactus graphs and an approximation factor of 𝒪(1) for graphs of bounded pathwidth.
Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi, Sumedha
ICALP1