All Outputs (3)

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, https://doi.org/10.1007/s00453-024-01238-z

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. (2023). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. European Journal of Combinatorics, 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.