Outputs (6)

Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle (2024)
Journal Article
Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2024). Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle. Algorithmica, 86(9), 2766-2785. https://doi.org/10.1007/s00453-024-01238-z

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C′≠C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if eve... Read More about Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle.

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal (2023)
Journal Article
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2024). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. European Journal of Combinatorics, 117, Article 103821. https://doi.org/10.1016/j.ejc.2023.103821

Linear read-once and related Boolean functions (2018)
Journal Article
Lozin, V., Razgon, I., Zamaraev, V., Zamaraeva, E., & Zolotykh, N. (2018). Linear read-once and related Boolean functions. Discrete Applied Mathematics, 250, 16-27. https://doi.org/10.1016/j.dam.2018.05.001

It is known that a positive Boolean function depending on variables has at least extremal points, i.e. minimal ones and maximal zeros. We show that has exactly extremal points if and only if it is linear read-once. The class of linear read-once funct... Read More about Linear read-once and related Boolean functions.

Independent transversals versus transversals
Presentation / Conference Contribution
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, December). Independent transversals versus transversals. Presented at EuroComb 2019, Bratislava, Slovakia

We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two... Read More about Independent transversals versus transversals.

Temporal vertex cover with a sliding time window
Presentation / Conference Contribution
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2018, July). Temporal vertex cover with a sliding time window. Presented at 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)., Prague, Czech Republic

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.

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
Presentation / Conference Contribution
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018, August). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Presented at 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if w... Read More about On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.