Ioannis Lamprou 0001

dblp:179/2278 · DBLP profile ↗
← Back
13ranked-venue papers
11as first author
4since 2021 · last 2026
0000-0001-5337-7336ORCID · verified

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

Theory of computation · 11 · 9 first-author · 4 since 2021Security and privacy · 1 · 1 first-author
YearPublicationVenuePosition
2026 Domination and Coverage Problems Under Vulnerability Constraints
Ioannis Lamprou 0001, Nikolaos Lazaropoulos, Ioannis Sigalas, Ioannis Vaxevanakis, Vassilis Zissimopoulos
IWOCA1
2022 Fault-Tolerant Total Domination via Submodular Function Approximation
Ioannis Lamprou 0001, Ioannis Sigalas, Ioannis Vaxevanakis, Vassilis Zissimopoulos
TAMC1
2021 Maximum rooted connected expansion
Ioannis Lamprou 0001, Russell Martin, Sven Schewe, Ioannis Sigalas, Vassilis Zissimopoulos
Theor. Comput. Sci.1
2021 Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
Ioannis Lamprou 0001, Ioannis Sigalas, Vassilis Zissimopoulos
Theor. Comput. Sci.1
2020 Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
Ioannis Lamprou 0001, Ioannis Sigalas, Vassilis Zissimopoulos
IWOCA1
2020 Cops and Robbers on Dynamic Graphs: Offline and Online Case
Stefan Balev, Juan Luis Jiménez Laredo, Ioannis Lamprou 0001, Yoann Pigné, Eric Sanlaville
SIROCCO3
2020 Fast two-robot disk evacuation with wireless communication
Ioannis Lamprou 0001, Russell Martin, Sven Schewe
Theor. Comput. Sci.1
2019 Eternally dominating large grids
Ioannis Lamprou 0001, Russell Martin, Sven Schewe
Theor. Comput. Sci.1
2018 Maximum Rooted Connected Expansion
abstract
Prefetching constitutes a valuable tool toward efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer Science 2014], where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of $k$ nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$ and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$ is connected, $S$ contains $v_0$ and the ratio $|N[S]|/|S|$ is maximized, where $N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all nodes in $S$ and all nodes with at least one neighbor in $S$. We prove that the problem is NP-hard even when the input graph $G$ is restricted to be a split graph. On the positive side, we demonstrate a polynomial time approximation scheme for split graphs. Furthermore, we present a $\frac{1}{6}(1-\frac{1}{e})$-approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomial-time algorithm for the special case of interval graphs.
Ioannis Lamprou 0001, Russell Martin, Sven Schewe, Ioannis Sigalas, Vassilis Zissimopoulos
MFCS1
2017 Perpetually Dominating Large Grids
Ioannis Lamprou 0001, Russell Martin, Sven Schewe
CIAC1
2017 Cover Time in Edge-Uniform Stochastically-Evolving Graphs
Ioannis Lamprou 0001, Russell Martin, Paul G. Spirakis
SSS1
2016 Fast Two-Robot Disk Evacuation with Wireless Communication
Ioannis Lamprou 0001, Russell Martin, Sven Schewe
DISC1
2015 Connected surveillance game
Frédéric Giroire, Ioannis Lamprou 0001, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes, R. Soares 0001
Theor. Comput. Sci.2