Demo Data from EDBT 2026 / reviewers in the wild / expert
Aida Aminian
dblp:397/9384
· DBLP profile ↗
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
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Approximation and online algorithms
approximation algorithms |
0.9 | 1 | 2025 | On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs · ICALP 2025 |
Approximation and online algorithms › approximation algorithms
constant-factor approximation |
0.9 | 1 | 2025 | 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.9 | 1 | 2025 | On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs · ICALP 2025 |
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth GraphsabstractIn 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 |
ICALP | 1 |