1 citations · 3 across the 7 of their papers we have counts for
5 papers · 1 filter
Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication
Christian Konrad, Peter Robinson, Viktor Zamaraev
We give lower bounds on the communication complexity of graph problems in the multi-party blackboard model. In this model, the edges of an -vertex input graph are partitioned am…
Matching in Stochastically Evolving Graphs
Eleni C. Akrida, Argyrios Deligkas, George B. Mertzios +2
This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a g…
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis +1
In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph and a Hamiltonian cycle of , how can we compute a second Hamiltonian…
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Christian Konrad, Viktor Zamaraev
We give deterministic distributed -approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algori…
Deleting edges to restrict the size of an epidemic in temporal networks
Jessica Enright, Kitty Meeks, George B. Mertzios +1
Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading ov…