11 citations · 15 across the 14 of their papers we have counts for
6 papers · 1 filter
Sliding Window Temporal Graph Coloring
George B. Mertzios, Hendrik Molter, Viktor Zamaraev
Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matchin…
Linear read-once and related Boolean functions
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
It is known that a positive Boolean function f depending on n variables has at least n + 1 extremal points, i.e. minimal ones and maximal zeros. We show that f has exactly n + 1 ex…
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…
Letter graphs and geometric grid classes of permutations: characterization and recognition
Bogdan Alecu, Vadim Lozin, Dominique de Werra +1
In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common…
Temporal Vertex Cover with a Sliding Time Window
Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis +1
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 stat…