Skip to main content

Research Repository

Advanced Search

All Outputs (18)

Narrowing and Stretching: Addressing the Challenge of Multi-track Programming (2022)
Presentation / Conference Contribution
Bradley, S., & Akrida, E. (2022). Narrowing and Stretching: Addressing the Challenge of Multi-track Programming. In Proceedings of the 6th Conference on Computing Education Practice CEP 2022 (1-4). https://doi.org/10.1145/3498343.3498344

Given the different amount of programming experience that students have arriving at university, some universities have introduced alternative multiple streams to teach programming. This approach was exemplified by Harvey Mudd College, who successfull... Read More about Narrowing and Stretching: Addressing the Challenge of Multi-track Programming.

Connected Subgraph Defense Games (2021)
Journal Article
Akrida, E. C., Deligkas, A., Melissourgos, T., & Spirakis, P. G. (2021). Connected Subgraph Defense Games. Algorithmica, 83(11), 3403-3431. https://doi.org/10.1007/s00453-021-00858-z

We study a security game over a network played between a defender and k attackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the networ... Read More about Connected Subgraph Defense Games.

The temporal explorer who returns to the base (2021)
Journal Article
Akrida, E., Mertzios, G., Spirakis, P., & Raptopoulos, C. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, 179-193. https://doi.org/10.1016/j.jcss.2021.04.001

We study here the problem of exploring a temporal graph when the underlying graph is a star. The aim of the exploration problem in a temporal star is finding a temporal walk which starts and finishes at the center of the star, and visits all leaves.... Read More about The temporal explorer who returns to the base.

How fast can we reach a target vertex in stochastic temporal graphs? (2020)
Journal Article
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zmaraev, V. (2020). How fast can we reach a target vertex in stochastic temporal graphs?. Journal of Computer and System Sciences, 114, 65-83. https://doi.org/10.1016/j.jcss.2020.05.005

Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) of G, where . In this paper we study stochastic temporal graphs, i.e. stoc... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

Connected Subgraph Defense Games (2019)
Book Chapter
Akrida, E. C., Deligkas, A., Melissourgos, T., & Spirakis, P. G. (2019). Connected Subgraph Defense Games. In Algorithmic Game Theory (216-236). Springer Verlag. https://doi.org/10.1007/978-3-030-30473-7_15

We study a security game over a network played between a defender and k attackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the networ... Read More about Connected Subgraph Defense Games.

Temporal vertex cover with a sliding time window (2019)
Journal Article
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108-123. https://doi.org/10.1016/j.jcss.2019.08.002

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels... Read More about Temporal vertex cover with a sliding time window.

How fast can we reach a target vertex in stochastic temporal graphs? (2019)
Presentation / Conference Contribution
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (131:1-131:14). https://doi.org/10.4230/lipics.icalp.2019.131

Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature, in the sense that the network structure undergoes discrete changes over time. Given a static underlying graph G=(V,E), a temporal graph on G is a s... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

On Verifying and Maintaining Connectivity of Interval Temporal Networks (2019)
Journal Article
Akrida, E. C., & Spirakis, P. G. (2019). On Verifying and Maintaining Connectivity of Interval Temporal Networks. Parallel Processing Letters, 29(02), Article 1950009. https://doi.org/10.1142/s0129626419500099

An interval temporal network is, informally speaking, a network whose links change with time. The term interval means that a link may exist for one or more time intervals, called availability intervals of the link, after which it does not exist (unti... Read More about On Verifying and Maintaining Connectivity of Interval Temporal Networks.

The temporal explorer who returns to the base (2019)
Presentation / Conference Contribution
Akrida, E., Mertzios, G., & Spirakis, P. (2019, December). The temporal explorer who returns to the base. Presented at 11th International Conference on Algorithms and Complexity (CIAC 2019), Rome, Italy

In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploration problem in a temporal star is to fin... Read More about The temporal explorer who returns to the base.

Temporal flows in temporal networks (2019)
Journal Article
Akrida, E. C., Czyzowicz, J., Gąsieniec, L., Kuszner, Ł., & Spirakis, P. G. (2019). Temporal flows in temporal networks. Journal of Computer and System Sciences, 103, 46-60. https://doi.org/10.1016/j.jcss.2019.02.003

We introduce temporal flows on temporal networks. We show that one can find the maximum amount of flow that can pass from a source vertex s to a sink vertex t up to a given time in Polynomial time. We provide a static Time-Extended network (TEG) of p... Read More about Temporal flows in temporal networks.

Temporal vertex cover with a sliding time window (2018)
Presentation / Conference Contribution
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2018). Temporal vertex cover with a sliding time window. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) : Prague, Czech Republic, July 9-13, 2018 ; proceedings (148:1-148:14). https://doi.org/10.4230/lipics.icalp.2018.148

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph G, a temporal graph can be represented via an assi... Read More about Temporal vertex cover with a sliding time window.

Temporal Flows in Temporal Networks (2017)
Presentation / Conference Contribution
Akrida, E. C., Czyzowicz, J., Gąsieniec, L., Kuszner, Ł., & Spirakis, P. G. (2017, December). Temporal Flows in Temporal Networks. Presented at 10th International Conference in Algorithms and Complexity, CIAC 2017, Athens, Greece

We introduce temporal flows on temporal networks [17, 19], i.e., networks the links of which exist only at certain moments of time. Such networks are ephemeral in the sense that no link exists after some time. Our flow model is new and differs from t... Read More about Temporal Flows in Temporal Networks.

The complexity of optimal design of temporally connected graphs (2017)
Journal Article
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2017). The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3), 907-944. https://doi.org/10.1007/s00224-017-9757-x

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u t... Read More about The complexity of optimal design of temporally connected graphs.

On temporally connected graphs of small cost (2016)
Presentation / Conference Contribution
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2015, September). On temporally connected graphs of small cost. Presented at 13th Workshop on Approximation and Online Algorithms (WAOA), Patras, Greece

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u t... Read More about On temporally connected graphs of small cost.

On Verifying and Maintaining Connectivity of Interval Temporal Networks (2015)
Presentation / Conference Contribution
Akrida, E. C., & Spirakis, P. G. (2015, December). On Verifying and Maintaining Connectivity of Interval Temporal Networks. Presented at Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), Patras, Greece

An interval temporal network is, informally speaking, a network whose links change with time. The term interval means that a link may exist for one or more time intervals, called availability intervals of the link, after which it does not exist (unti... Read More about On Verifying and Maintaining Connectivity of Interval Temporal Networks.

Ephemeral networks with random availability of links: The case of fast networks (2015)
Journal Article
Akrida, E., Gąsieniec, L., Mertzios, G., & Spirakis, P. (2016). Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87, 109-120. https://doi.org/10.1016/j.jpdc.2015.10.002

We consider here a model of temporal networks, the links of which are available only at certain moments in time, chosen randomly from a subset of the positive integers. We define the notion of the Temporal Diameter of such networks. We also define fa... Read More about Ephemeral networks with random availability of links: The case of fast networks.

Ephemeral networks with random availability of links: diameter and connectivity (2014)
Presentation / Conference Contribution
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2014). Ephemeral networks with random availability of links: diameter and connectivity. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (267-276). https://doi.org/10.1145/2612669.2612693

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum... Read More about Ephemeral networks with random availability of links: diameter and connectivity.