Dr Viktor Zamaraev

Lecturer Computer Science

+44 (0)151 794 0606 Ext. 40606
Work email Viktor.Zamaraev@liverpool.ac.uk
Personal Websitehttps://www.victorzamaraev.com/

Publications

Filter the publication list

Filter list by type

Show all
Journal article
Conference paper
Chapter
Other

2024

Sharp Thresholds in Random Simple Temporal Graphs (Journal article)

Casteigts, A., Raskin, M., Renken, M., & Zamaraev, V. (2024). Sharp Thresholds in Random Simple Temporal Graphs. SIAM Journal on Computing, 53(2), 346-388. doi:10.1137/22m1511916

DOI: 10.1137/22m1511916

The Treewidth and Pathwidth of Graph Unions (Journal article)

Alecu, B., Lozin, V. V., Quiroz, D. A., Rabinovich, R., Razgon, I., & Zamaraev, V. (2024). The Treewidth and Pathwidth of Graph Unions. SIAM Journal on Discrete Mathematics, 38(1), 261-276. doi:10.1137/22m1524047

DOI: 10.1137/22m1524047

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions (Preprint)

Functionality of Box Intersection Graphs (Journal article)

Dallard, C., Lozin, V., Milanič, M., Štorgel, K., & Zamaraev, V. (2024). Functionality of Box Intersection Graphs. Results in Mathematics, 79(1). doi:10.1007/s00025-023-02075-2

DOI: 10.1007/s00025-023-02075-2

Union-closed sets and Horn Boolean functions (Journal article)

Lozin, V., & Zamaraev, V. (2024). Union-closed sets and Horn Boolean functions. Journal of Combinatorial Theory, Series A, 202, 105818. doi:10.1016/j.jcta.2023.105818

DOI: 10.1016/j.jcta.2023.105818

Graphs with minimum fractional domatic number (Journal article)

Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. doi:10.1016/j.dam.2023.10.020

DOI: 10.1016/j.dam.2023.10.020

Accelerating Material Property Prediction using Generically Complete Isometry Invariants (Preprint)

Accelerating Material Property Prediction using Generically Complete Isometry Invariants. (Preprint)

Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank (Conference Paper)

Harms, N., & Zamaraev, V. (2024). Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank. In Unknown Conference (pp. 1810-1833). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977912.72

DOI: 10.1137/1.9781611977912.72

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes (Conference Paper)

Bonnet, E., Duron, J., Sylvester, J., Zamaraev, V., & Zhukovskii, M. (2024). Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. In Unknown Conference (pp. 1147-1165). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977912.44

DOI: 10.1137/1.9781611977912.44

2023

Computing maximum matchings in temporal graphs (Journal article)

Mertzios, G. B., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, 137, 1-19. doi:10.1016/j.jcss.2023.04.005

DOI: 10.1016/j.jcss.2023.04.005

Tight bounds on adjacency labels for monotone graph classes (Preprint)

Graph parameters, implicit representations and factorial properties (Journal article)

Alecu, B., Alekseev, V. E., Atminas, A., Lozin, V., & Zamaraev, V. (2023). Graph parameters, implicit representations and factorial properties. DISCRETE MATHEMATICS, 346(10). doi:10.1016/j.disc.2023.113573

DOI: 10.1016/j.disc.2023.113573

Giant Components in Random Temporal Graphs (Conference Paper)

Becker, R., Crescenzi, P., Renken, M., Zamaraev, V., Casteigts, A., Kodric, B., & Raskin, M. (2023). Giant Components in Random Temporal Graphs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 275. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.29

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.29

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes (Preprint)

Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank (Preprint)

Optimal Adjacency Labels for Subgraphs of Cartesian Products (Conference Paper)

Esperet, L., Harms, N., & Zamaraev, V. (2023). Optimal Adjacency Labels for Subgraphs of Cartesian Products. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 261. doi:10.4230/LIPIcs.ICALP.2023.57

DOI: 10.4230/LIPIcs.ICALP.2023.57

Graph parameters, implicit representations and factorial properties (Preprint)

Graphs with minimum fractional domatic number (Preprint)

Succinct Permutation Graphs (Journal article)

Tsakalidis, K., Wild, S., & Zamaraev, V. (n.d.). Succinct Permutation Graphs. Algorithmica. doi:10.1007/s00453-022-01039-2

DOI: 10.1007/s00453-022-01039-2

Functionality of box intersection graphs (Preprint)

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal (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. doi:10.1016/j.ejc.2023.103821

DOI: 10.1016/j.ejc.2023.103821

Functionality of box intersection graphs. (Preprint)

Giant Components in Random Temporal Graphs. (Conference Paper)

Becker, R., Casteigts, A., Crescenzi, P., Kodric, B., Renken, M., Raskin, M., & Zamaraev, V. (2023). Giant Components in Random Temporal Graphs.. In N. Megow, & A. D. Smith (Eds.), APPROX/RANDOM Vol. 275 (pp. 29:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-296-9

Graph parameters, implicit representations and factorial properties. (Preprint)

Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank. (Preprint)

Small But Unwieldy. (Preprint)

Tight bounds on adjacency labels for monotone graph classes. (Preprint)

2022

Compact Graph Representation of crystal structures using Point-wise Distance Distributions (Preprint)

Distributed minimum vertex coloring and maximum independent set in chordal graphs (Journal article)

Konrad, C., & Zamaraev, V. (2022). Distributed minimum vertex coloring and maximum independent set in chordal graphs. THEORETICAL COMPUTER SCIENCE, 922, 486-502. doi:10.1016/j.tcs.2022.04.047

DOI: 10.1016/j.tcs.2022.04.047

Randomized Communication and Implicit Graph Representations (Conference Paper)

Harms, N., Wild, S., & Zamaraev, V. (2022). Randomized Communication and Implicit Graph Representations. In PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) (pp. 1220-1233). doi:10.1145/3519935.3519978

DOI: 10.1145/3519935.3519978

Optimal Adjacency Labels for Subgraphs of Cartesian Products (Preprint)

DOI: 10.48550/arxiv.2206.02872

Optimal Adjacency Labels for Subgraphs of Cartesian Products (Conference Paper)

Esperet, L., Harms, N., & Zamaraev, V. (2022). Optimal Adjacency Labels for Subgraphs of Cartesian Products. Retrieved from http://arxiv.org/abs/2206.02872v2

Giant Components in Random Temporal Graphs (Preprint)

Faster Exploration of Some Temporal Graphs (Conference Paper)

Adamson, D., Gusev, V. V., Malyshev, D., & Zamaraev, V. (2022). Faster Exploration of Some Temporal Graphs. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 221. doi:10.4230/LIPIcs.SAND.2022.5

DOI: 10.4230/LIPIcs.SAND.2022.5

The treewidth and pathwidth of graph unions (Report)

Alecu, B., Lozin, V., Quiroz, D. A., Rabinovich, R., Razgon, I., & Zamaraev, V. (2022). The treewidth and pathwidth of graph unions. Retrieved from http://dx.doi.org/10.1137/22M1524047

The treewidth and pathwidth of graph unions. (Preprint)

Compact Graph Representation of molecular crystals using Point-wise Distance Distributions. (Preprint)

Graph Parameters, Implicit Representations and Factorial Properties (Conference Paper)

Alecu, B., Alekseev, V. E., Atminas, A., Lozin, V., & Zamaraev, V. (2022). Graph Parameters, Implicit Representations and Factorial Properties. In COMBINATORIAL ALGORITHMS (IWOCA 2022) Vol. 13270 (pp. 60-72). doi:10.1007/978-3-031-06678-8_5

DOI: 10.1007/978-3-031-06678-8_5

Letter graphs and geometric grid classes of permutations (Journal article)

Alecu, B., Ferguson, R., Kante, M. M., Lozin, V. V., Vatter, V., & Zamaraev, V. (2022). LETTER GRAPHS AND GEOMETRIC GRID CLASSES OF PERMUTATIONS. SIAM JOURNAL ON DISCRETE MATHEMATICS, 36(4), 2774-2797. doi:10.1137/21M1449646

DOI: 10.1137/21M1449646

On Boolean threshold functions with minimum specification number (Journal article)

Lozin, V., Zamaraev, V., Zamaraeva, E., & Zolotykh, N. Y. (2022). On Boolean threshold functions with minimum specification number. INFORMATION AND COMPUTATION, 289. doi:10.1016/j.ic.2022.104926

DOI: 10.1016/j.ic.2022.104926

2021

Randomized Communication and Implicit Graph Representations (Conference Paper)

Harms, N., Wild, S., & Zamaraev, V. (2021). Randomized Communication and Implicit Graph Representations. Retrieved from http://arxiv.org/abs/2111.03639v3

Randomized Communication and Implicit Graph Representations (Preprint)

DOI: 10.48550/arxiv.2111.03639

Sliding window temporal graph coloring (Journal article)

Mertzios, G. B., Molter, H., & Zamaraev, V. (2021). Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120, 97-115. doi:10.1016/j.jcss.2021.03.005

DOI: 10.1016/j.jcss.2021.03.005

Deleting edges to restrict the size of an epidemic in temporal networks (Journal article)

Enright, J., Meeks, K., Mertzios, G. B., & Zamaraev, V. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 119, 60-77. doi:10.1016/j.jcss.2021.01.007

DOI: 10.1016/j.jcss.2021.01.007

Letter graphs and geometric grid classes of permutations (Preprint)

Graph classes with linear Ramsey numbers (Journal article)

Alecu, B., Atminas, A., Lozin, V., & Zamaraev, V. (2021). Graph classes with linear Ramsey numbers. Discrete Mathematics, 344(4). doi:10.1016/j.disc.2021.112307

DOI: 10.1016/j.disc.2021.112307

Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication (Preprint)

Randomized Communication and the Implicit Graph Conjecture. (Journal article)

Harms, N., Wild, S., & Zamaraev, V. (2021). Randomized Communication and the Implicit Graph Conjecture.. CoRR, abs/2111.03639.

Sharp Thresholds in Random Simple Temporal Graphs. (Conference Paper)

Casteigts, A., Raskin, M., Renken, M., & Zamaraev, V. (2021). Sharp Thresholds in Random Simple Temporal Graphs.. In FOCS (pp. 319-326). IEEE. Retrieved from https://doi.org/10.1109/FOCS52979.2022

2020

How fast can we reach a target vertex in stochastic temporal graphs? (Journal article)

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

DOI: 10.1016/j.jcss.2020.05.005

Sharp Thresholds in Random Simple Temporal Graphs (Conference Paper)

Casteigts, A., Raskin, M., Renken, M., & Zamaraev, V. (2022). Sharp Thresholds in Random Simple Temporal Graphs. In 2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021) (pp. 319-326). doi:10.1109/FOCS52979.2021.00040

DOI: 10.1109/FOCS52979.2021.00040

Sharp Thresholds in Random Simple Temporal Graphs (Preprint)

DOI: 10.48550/arxiv.2011.03738

Succinct Permutation Graphs (Preprint)

DOI: 10.48550/arxiv.2010.04108

Succinct Permutation Graphs (Report)

Tsakalidis, K., Wild, S., & Zamaraev, V. (2020). Succinct Permutation Graphs. Retrieved from http://dx.doi.org/10.1007/s00453-022-01039-2

Letter graphs and geometric grid classes of permutations: Characterization and recognition (Report)

Alecu, B., Lozin, V., de Werra, D., & Zamaraev, V. (2020). Letter graphs and geometric grid classes of permutations: Characterization and recognition. doi:10.1016/j.dam.2020.01.038

DOI: 10.1016/j.dam.2020.01.038

Letter graphs and geometric grid classes of permutations: Characterization and recognition. (Journal article)

Alecu, B., Lozin, V. V., Werra, D. D., & Zamaraev, V. (2020). Letter graphs and geometric grid classes of permutations: Characterization and recognition.. Discret. Appl. Math., 283, 482-494.

Between clique-width and linear clique-width of bipartite graphs (Journal article)

Alecu, B., Kante, M. M., Lozin, V., & Zamaraev, V. (2020). Between clique-width and linear clique-width of bipartite graphs. DISCRETE MATHEMATICS, 343(8). doi:10.1016/j.disc.2020.111926

DOI: 10.1016/j.disc.2020.111926

Matching in Stochastically Evolving Graphs (Report)

Akrida, E. C., Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Matching in Stochastically Evolving Graphs. Retrieved from http://arxiv.org/abs/2005.08263v1

Matching in Stochastically Evolving Graphs (Preprint)

DOI: 10.48550/arxiv.2005.08263

Clique-Width for Graph Classes Closed under Complementation (Journal article)

Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2020). Clique-Width for Graph Classes Closed under Complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. doi:10.1137/18m1235016

DOI: 10.1137/18m1235016

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle (Journal article)

Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. Retrieved from http://arxiv.org/abs/2004.06036v2

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle (Preprint)

DOI: 10.48550/arxiv.2004.06036

Independent domination versus weighted independent domination. (Journal article)

Lozin, V. V., Malyshev, D. S., Mosca, R., & Zamaraev, V. (2020). Independent domination versus weighted independent domination.. Inf. Process. Lett., 156, 105914. doi:10.1016/j.ipl.2020.105914

DOI: 10.1016/j.ipl.2020.105914

Temporal Vertex Cover with a Sliding Time Window (Journal article)

Akrida, E., Mertzios, G. B., Spirakis, P., & Zamaraev, V. (2020). Temporal Vertex Cover with a Sliding Time Window. Journal of Computer and System Sciences, 107, 108-123. doi:10.1016/j.jcss.2019.08.002

DOI: 10.1016/j.jcss.2019.08.002

Computing Maximum Matchings in Temporal Graphs. (Conference Paper)

Mertzios, G. B., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020). Computing Maximum Matchings in Temporal Graphs.. In C. Paul, & M. Bläser (Eds.), STACS Vol. 154 (pp. 27:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-140-5

DOI: 10.4230/LIPIcs.STACS.2020.27

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. (Conference Paper)

Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle.. In J. Esparza, & D. Král' (Eds.), MFCS Vol. 170 (pp. 27:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-159-7

DOI: 10.4230/LIPIcs.MFCS.2020.27

2019

Graph classes with linear Ramsey numbers (Preprint)

DOI: 10.48550/arxiv.1910.12109

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal (Conference Paper)

Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. Retrieved from http://arxiv.org/abs/1910.05254v1

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal (Preprint)

DOI: 10.48550/arxiv.1910.05254

INDEPENDENT TRANSVERSALS VERSUS TRANSVERSALS (Conference Paper)

Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). INDEPENDENT TRANSVERSALS VERSUS TRANSVERSALS. In ACTA MATHEMATICA UNIVERSITATIS COMENIANAE Vol. 88 (pp. 585-591). Retrieved from https://www.webofscience.com/

Linear Programming Complementation (Preprint)

Computing Maximum Matchings in Temporal Graphs (Preprint)

DOI: 10.48550/arxiv.1905.05304

Computing Maximum Matchings in Temporal Graphs (Conference Paper)

Mertzios, G. B., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020). Computing Maximum Matchings in Temporal Graphs. In 37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020) Vol. 154. doi:10.4230/LIPIcs.STACS.2020.27

DOI: 10.4230/LIPIcs.STACS.2020.27

How fast can we reach a target vertex in stochastic temporal graphs? (Journal article)

Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. Retrieved from http://arxiv.org/abs/1903.03636v1

How fast can we reach a target vertex in stochastic temporal graphs? (Preprint)

DOI: 10.48550/arxiv.1903.03636

Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks. (Conference Paper)

Enright, J. A., Meeks, K., Mertzios, G. B., & Zamaraev, V. (2019). Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks.. In P. Rossmanith, P. Heggernes, & J. -P. Katoen (Eds.), MFCS Vol. 138 (pp. 57:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-117-7

Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. (Conference Paper)

Konrad, C., & Zamaraev, V. (2019). Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs.. In P. Rossmanith, P. Heggernes, & J. -P. Katoen (Eds.), MFCS Vol. 138 (pp. 21:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-117-7

Sliding Window Temporal Graph Coloring (Conference Paper)

Mertzios, G. B., Molter, H., & Zamaraev, V. (n.d.). Sliding Window Temporal Graph Coloring. In Proceedings of the AAAI Conference on Artificial Intelligence Vol. 33 (pp. 7667-7674). Association for the Advancement of Artificial Intelligence (AAAI). doi:10.1609/aaai.v33i01.33017667

DOI: 10.1609/aaai.v33i01.33017667

2018

Sliding Window Temporal Graph Coloring (Preprint)

DOI: 10.48550/arxiv.1811.04753

Sliding Window Temporal Graph Coloring (Conference Paper)

Mertzios, G. B., Molter, H., & Zamaraev, V. (2019). Sliding Window Temporal Graph Coloring. In THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE (pp. 7667-7674). Retrieved from https://www.webofscience.com/

Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs (Conference Paper)

Konrad, C., & Zamaraev, V. (2018). Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. In PODC'18: PROCEEDINGS OF THE 2018 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (pp. 159-161). doi:10.1145/3212734.3212787

DOI: 10.1145/3212734.3212787

Linear read-once and related Boolean functions (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. doi:10.1016/j.dam.2018.05.001

DOI: 10.1016/j.dam.2018.05.001

Linear read-once and related Boolean functions (Preprint)

DOI: 10.48550/arxiv.1805.10159

Deleting edges to restrict the size of an epidemic in temporal networks (Conference Paper)

Enright, J., Meeks, K., Mertzios, G. B., & Zamaraev, V. (2018). Deleting edges to restrict the size of an epidemic in temporal networks. Retrieved from http://arxiv.org/abs/1805.06836v2

Deleting edges to restrict the size of an epidemic in temporal networks (Preprint)

DOI: 10.48550/arxiv.1805.06836

Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs (Conference Paper)

Konrad, C., & Zamaraev, V. (2018). Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. Retrieved from http://arxiv.org/abs/1805.04544v1

Well-quasi-ordering versus clique-width (Journal article)

Lozin, V., Razgon, I., & Zamaraev, V. (2018). Well-quasi-ordering versus clique-width. JOURNAL OF COMBINATORIAL THEORY SERIES B, 130, 1-18. doi:10.1016/j.jctb.2017.09.012

DOI: 10.1016/j.jctb.2017.09.012

Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition (Conference Paper)

Alecu, B., Lozin, V., Zamaraev, V., & de Werra, D. (2018). Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition. In COMBINATORIAL ALGORITHMS, IWOCA 2017 Vol. 10765 (pp. 195-205). doi:10.1007/978-3-319-78825-8_16

DOI: 10.1007/978-3-319-78825-8_16

Letter graphs and geometric grid classes of permutations: characterization and recognition (Preprint)

DOI: 10.48550/arxiv.1804.11217

Temporal Vertex Cover with a Sliding Time Window (Preprint)

DOI: 10.48550/arxiv.1802.07103

Temporal Vertex Cover with a Sliding Time Window (Conference Paper)

Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2018). Temporal Vertex Cover with a Sliding Time Window. Retrieved from http://arxiv.org/abs/1802.07103v3

Dominating induced matchings in graphs containing no long claw. (Journal article)

Hertz, A., Lozin, V. V., Ries, B., Zamaraev, V., & Werra, D. D. (2018). Dominating induced matchings in graphs containing no long claw.. J. Graph Theory, 88, 18-39. doi:10.1002/jgt.22182

DOI: 10.1002/jgt.22182

Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition (Chapter)

Alecu, B., Lozin, V., Zamaraev, V., & de Werra, D. (2018). Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition. In Combinatorial Algorithms (Vol. 10765, pp. 195-205). Springer Nature. doi:10.1007/978-3-319-78825-8_16

DOI: 10.1007/978-3-319-78825-8_16

Linear Clique-Width of Bi-complement Reducible Graphs (Conference Paper)

Alecu, B., Lozin, V., & Zamaraev, V. (2018). Linear Clique-Width of Bi-complement Reducible Graphs. In COMBINATORIAL ALGORITHMS, IWOCA 2018 Vol. 10979 (pp. 14-25). doi:10.1007/978-3-319-94667-2_2

DOI: 10.1007/978-3-319-94667-2_2

Linear Ramsey Numbers (Conference Paper)

Atminas, A., Lozin, V., & Zamaraev, V. (2018). Linear Ramsey Numbers. In COMBINATORIAL ALGORITHMS, IWOCA 2018 Vol. 10979 (pp. 26-38). doi:10.1007/978-3-319-94667-2_3

DOI: 10.1007/978-3-319-94667-2_3

Linear read-once and related Boolean functions. (Journal article)

Lozin, V. V., Razgon, I., Zamaraev, V., Zamaraeva, E., & Zolotykh, N. Y. (2018). Linear read-once and related Boolean functions.. Discret. Appl. Math., 250, 16-27.

2017

The structure and the number of P7-free bipartite graphs (Conference Paper)

Lozin, V., & Zamaraev, V. (2017). The structure and the number of P7-free bipartite graphs. In Electronic Notes in Discrete Mathematics Vol. 61 (pp. 827-833). Elsevier BV. doi:10.1016/j.endm.2017.07.042

DOI: 10.1016/j.endm.2017.07.042

Specifying a positive threshold function via extremal points (Journal article)

Lozin, V., Razgon, I., Zamaraev, V., Zamaraeva, E., & Zolotykh, N. Y. (2017). Specifying a positive threshold function via extremal points. Retrieved from http://arxiv.org/abs/1706.01747v1

Specifying a positive threshold function via extremal points (Preprint)

DOI: 10.48550/arxiv.1706.01747

Clique-Width for Graph Classes Closed under Complementation (Preprint)

DOI: 10.48550/arxiv.1705.07681

Clique-Width for Graph Classes Closed under Complementation (Report)

Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017). Clique-Width for Graph Classes Closed under Complementation. Retrieved from http://arxiv.org/abs/1705.07681v2

Infinitely many minimal classes of graphs of unbounded clique-width (Preprint)

DOI: 10.48550/arxiv.1701.08857

Infinitely many minimal classes of graphs of unbounded clique-width (Journal article)

Collins, A., Foniok, J., Korpelainen, N., Lozin, V., & Zamaraev, V. (2018). Infinitely many minimal classes of graphs of unbounded clique-width. DISCRETE APPLIED MATHEMATICS, 248, 145-152. doi:10.1016/j.dam.2017.02.012

DOI: 10.1016/j.dam.2017.02.012

Clique-Width for Graph Classes Closed under Complementation. (Conference Paper)

Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017). Clique-Width for Graph Classes Closed under Complementation.. In K. G. Larsen, H. L. Bodlaender, & J. -F. Raskin (Eds.), MFCS Vol. 83 (pp. 73:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-046-0

New Results on Weighted Independent Domination (Conference Paper)

Lozin, V., Malyshev, D., Mosca, R., & Zamaraev, V. (2017). New Results on Weighted Independent Domination. In GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017) Vol. 10520 (pp. 399-411). doi:10.1007/978-3-319-68705-6_30

DOI: 10.1007/978-3-319-68705-6_30

Specifying a positive threshold function via extremal points. (Conference Paper)

Lozin, V. V., Razgon, I., Zamaraev, V., Zamaraeva, E., & Zolotykh, N. Y. (2017). Specifying a positive threshold function via extremal points.. In S. Hanneke, & L. Reyzin (Eds.), ALT Vol. 76 (pp. 208-222). PMLR. Retrieved from http://proceedings.mlr.press/v76/

2016

Upper Domination: Towards a Dichotomy Through Boundary Properties (Journal article)

AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B., & Zamaraev, V. (2018). Upper Domination: Towards a Dichotomy Through Boundary Properties. ALGORITHMICA, 80(10), 2799-2817. doi:10.1007/s00453-017-0346-9

DOI: 10.1007/s00453-017-0346-9

Upper Domination: towards a dichotomy through boundary properties (Preprint)

DOI: 10.48550/arxiv.1609.01510

The structure and the number of $P_7$-free bipartite graphs (Preprint)

DOI: 10.48550/arxiv.1607.08782

The structure and the number of P7-free bipartite graphs (Journal article)

Lozin, V., & Zamaraev, V. (2017). The structure and the number of P7-free bipartite graphs. EUROPEAN JOURNAL OF COMBINATORICS, 65, 143-153. doi:10.1016/j.ejc.2017.05.008

DOI: 10.1016/j.ejc.2017.05.008

More results on weighted independent domination (Journal article)

Lozin, V., Malyshev, D., Mosca, R., & Zamaraev, V. (2017). More results on weighted independent domination. THEORETICAL COMPUTER SCIENCE, 700, 63-74. doi:10.1016/j.tcs.2017.08.007

DOI: 10.1016/j.tcs.2017.08.007

More results on weighted independent domination (Preprint)

DOI: 10.48550/arxiv.1602.09124

On Forbidden Induced Subgraphs for Unit Disk Graphs (Journal article)

Atminas, A., & Zamaraev, V. (2018). On Forbidden Induced Subgraphs for Unit Disk Graphs. Discrete and Computational Geometry: an international journal of mathematics and computer science, 60, 57-97. doi:10.1007/s00454-018-9968-1

DOI: 10.1007/s00454-018-9968-1

On forbidden induced subgraphs for unit disk graphs (Preprint)

DOI: 10.48550/arxiv.1602.08148

A Boundary Property for Upper Domination (Conference Paper)

AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B., & Zamaraev, V. (2016). A Boundary Property for Upper Domination. In Combinatorial Algorithms Vol. 9843 (pp. 229-240). doi:10.1007/978-3-319-44543-4_18

DOI: 10.1007/978-3-319-44543-4_18

2015

Dominating induced matchings in graphs containing no long claw (Journal article)

Hertz, A., Lozin, V., Ries, B., Zamaraev, V., & de Werra, D. (2018). Dominating induced matchings in graphs containing no long claw. JOURNAL OF GRAPH THEORY, 88(1), 18-39. doi:10.1002/jgt.22182

DOI: 10.1002/jgt.22182

Well-quasi-ordering Does Not Imply Bounded Clique-width (Journal article)

Lozin, V. V., Razgon, I., & Zamaraev, V. (2016). Well-quasi-ordering Does Not Imply Bounded Clique-width. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 9224, 351-359. doi:10.1007/978-3-662-53174-7_25

DOI: 10.1007/978-3-662-53174-7_25

Well-quasi-ordering does not imply bounded clique-width (Preprint)

Boundary Properties of Factorial Classes of Graphs (Journal article)

Lozin, V. V., & Zamaraev, V. (2015). Boundary Properties of Factorial Classes of Graphs. JOURNAL OF GRAPH THEORY, 78(3), 207-218. doi:10.1002/jgt.21799

DOI: 10.1002/jgt.21799

A tolerance-based heuristic approach for the weighted independent set problem (Journal article)

Goldengorin, B. I., Malyshev, D. S., Pardalos, P. M., & Zamaraev, V. A. (2015). A tolerance-based heuristic approach for the weighted independent set problem. JOURNAL OF COMBINATORIAL OPTIMIZATION, 29(2), 433-450. doi:10.1007/s10878-013-9606-z

DOI: 10.1007/s10878-013-9606-z

Well-quasi-ordering Does Not Imply Bounded Clique-width. (Conference Paper)

Lozin, V. V., Razgon, I., & Zamaraev, V. (2015). Well-quasi-ordering Does Not Imply Bounded Clique-width.. In E. W. Mayr (Ed.), WG Vol. 9224 (pp. 351-359). Springer. Retrieved from https://doi.org/10.1007/978-3-662-53174-7

2014

Combinatorics and Algorithms for Augmenting Graphs (Journal article)

Dabrowski, K. K., Lozin, V. V., de Werra, D., & Zamaraev, V. (2016). Combinatorics and Algorithms for Augmenting Graphs. GRAPHS AND COMBINATORICS, 32(4), 1339-1352. doi:10.1007/s00373-015-1660-0

DOI: 10.1007/s00373-015-1660-0

Combinatorics and algorithms for augmenting graphs (Preprint)

DOI: 10.48550/arxiv.1410.8774

Implicit representations and factorial properties of graphs (Journal article)

Atminas, A., Collins, A., Lozin, V., & Zamaraev, V. (2015). Implicit representations and factorial properties of graphs. DISCRETE MATHEMATICS, 338(2), 164-179. doi:10.1016/j.disc.2014.09.008

DOI: 10.1016/j.disc.2014.09.008

Market Graph and Markowitz Model (Chapter)

Kalyagin, V., Koldanov, A., Koldanov, P., & Zamaraev, V. (2014). Market Graph and Markowitz Model. In Optimization in Science and Engineering (pp. 293-306). Springer New York. doi:10.1007/978-1-4939-0808-0_15

DOI: 10.1007/978-1-4939-0808-0_15

Locally bounded coverings and factorial properties of graphs (vol 33, pg 534, 2012) (Journal article)

Lozin, V. V., Mayhill, C., & Zamaraev, V. (2014). Locally bounded coverings and factorial properties of graphs (vol 33, pg 534, 2012). EUROPEAN JOURNAL OF COMBINATORICS, 40, 168. doi:10.1016/j.ejc.2014.03.004

DOI: 10.1016/j.ejc.2014.03.004

Network Structures Uncertainty for Different Markets (Chapter)

Kalyagin, V. A., Koldanov, P. A., & Zamaraev, V. A. (2014). Network Structures Uncertainty for Different Markets. In NETWORK MODELS IN ECONOMICS AND FINANCE (Vol. 100, pp. 181-197). doi:10.1007/978-3-319-09683-4_10

DOI: 10.1007/978-3-319-09683-4_10

Social Networks and the Economics of Sports (Book)

Pardalos, P. M., & Zamaraev, V. (Eds.) (2014). Social Networks and the Economics of Sports. Springer International Publishing. doi:10.1007/978-3-319-08440-4

DOI: 10.1007/978-3-319-08440-4

The Impact of Social Networks on Sports (Chapter)

Pardalos, P. M., & Zamaraev, V. (2014). The Impact of Social Networks on Sports. In Social Networks and the Economics of Sports (pp. 1-8). Springer International Publishing. doi:10.1007/978-3-319-08440-4_1

DOI: 10.1007/978-3-319-08440-4_1

2013

Measures of uncertainty in market network analysis (Journal article)

Kalyagin, V. A., Koldanov, A. P., Koldanov, P. A., Pardalos, P. M., & Zamaraev, V. A. (2014). Measures of uncertainty in market network analysis. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 413, 59-70. doi:10.1016/j.physa.2014.06.054

DOI: 10.1016/j.physa.2014.06.054

2012

On factorial properties of chordal bipartite graphs (Journal article)

Dabrowski, K., Lozin, V. V., & Zamaraev, V. (2012). On factorial properties of chordal bipartite graphs. DISCRETE MATHEMATICS, 312(16), 2457-2465. doi:10.1016/j.disc.2012.04.010

DOI: 10.1016/j.disc.2012.04.010

Locally bounded coverings and factorial properties of graphs (Journal article)

Lozin, V. V., Mayhill, C., & Zamaraev, V. (2012). Locally bounded coverings and factorial properties of graphs. EUROPEAN JOURNAL OF COMBINATORICS, 33(4), 534-543. doi:10.1016/j.ejc.2011.10.006

DOI: 10.1016/j.ejc.2011.10.006

2011

On estimation of the number of graphs in some hereditary classes (Journal article)

Zamaraev, V. A. (2011). On estimation of the number of graphs in some hereditary classes. Discrete Mathematics and Applications, 21(4). doi:10.1515/dma.2011.027

DOI: 10.1515/dma.2011.027

A note on the speed of hereditary graph properties (Journal article)

Lozin, V. V., Mayhill, C., & Zamaraev, V. (2011). A note on the speed of hereditary graph properties. ELECTRONIC JOURNAL OF COMBINATORICS, 18(1). Retrieved from https://www.webofscience.com/

Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph (Journal article)

Zamaraev, V. (2011). Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph. Moscow Journal of Combinatorics and Number Theory, 1(3), 69-78.