Publications
2024
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Bonnet, É., Duron, J., Sylvester, J., Zamaraev, V., & Zhukovskii, M. (2024). Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. SIAM Journal on Computing, 53(5), 1578-1601. doi:10.1137/23m1618661
Optimal Adjacency Labels for Subgraphs of Cartesian Products
Esperet, L., Harms, N., & Zamaraev, V. (2024). Optimal Adjacency Labels for Subgraphs of Cartesian Products. SIAM Journal on Discrete Mathematics, 38(3), 2181-2193. doi:10.1137/23m1587713
Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle
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. doi:10.1007/s00453-024-01238-z
Symmetric-Difference (Degeneracy) and Signed Tree Models
Bonnet, É., Duron, J., Sylvester, J., & Zamaraev, V. (2024). Symmetric-Difference (Degeneracy) and Signed Tree Models. In Leibniz International Proceedings in Informatics Vol. 306. Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.MFCS.2024.24
Symmetric-Difference (Degeneracy) and Signed Tree Models
Bonnet, É., Duron, J., Sylvester, J., & Zamaraev, V. (2024). Symmetric-Difference (Degeneracy) and Signed Tree Models. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 306. doi:10.4230/LIPIcs.MFCS.2024.32
Tight Bounds on Adjacency Labels for Monotone Graph Classes
Bonnet, É., Duron, J., Sylvester, J., Zamaraev, V., & Zhukovskii, M. (2024). Tight Bounds on Adjacency Labels for Monotone Graph Classes. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 297. doi:10.4230/LIPIcs.ICALP.2024.31
Material Property Prediction Using Graphs Based on Generically Complete Isometry Invariants
Balasingham, J., Zamaraev, V., & Kurlin, V. (2024). Material Property Prediction Using Graphs Based on Generically Complete Isometry Invariants. Integrating Materials and Manufacturing Innovation, 13(2), 555-568. doi:10.1007/s40192-024-00351-9
Accelerating material property prediction using generically complete isometry invariants.
Balasingham, J., Zamaraev, V., & Kurlin, V. (2024). Accelerating material property prediction using generically complete isometry invariants.. Scientific reports, 14(1), 10132. doi:10.1038/s41598-024-59938-z
Sharp Thresholds in Random Simple Temporal Graphs
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
The Treewidth and Pathwidth of Graph Unions
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
Functionality of Box Intersection Graphs
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
Union-closed sets and Horn Boolean functions
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
Graphs with minimum fractional domatic number
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
Accelerating Material Property Prediction using Generically Complete Isometry Invariants.
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
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
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
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
2023
Computing maximum matchings in temporal graphs
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
Graph parameters, implicit representations and factorial properties
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
Giant Components in Random Temporal Graphs
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
Optimal Adjacency Labels for Subgraphs of Cartesian Products
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
Succinct Permutation Graphs
Tsakalidis, K., Wild, S., & Zamaraev, V. (n.d.). Succinct Permutation Graphs. Algorithmica. doi:10.1007/s00453-022-01039-2
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
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
Functionality of box intersection graphs.
Giant Components in Random Temporal Graphs.
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.
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank.
Small But Unwieldy.
Tight bounds on adjacency labels for monotone graph classes.
2022
On Boolean threshold functions with minimum specification number
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
Distributed minimum vertex coloring and maximum independent set in chordal graphs
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
Randomized Communication and Implicit Graph Representations
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
Optimal Adjacency Labels for Subgraphs of Cartesian Products
Optimal Adjacency Labels for Subgraphs of Cartesian Products
Esperet, L., Harms, N., & Zamaraev, V. (2022). Optimal Adjacency Labels for Subgraphs of Cartesian Products. In SIAM Journal on Discrete Mathematics 38(3) (2024), 2181-2193. Retrieved from http://dx.doi.org/10.1137/23M1587713
Faster Exploration of Some Temporal Graphs
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
The treewidth and pathwidth of graph unions
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.
Compact Graph Representation of molecular crystals using Point-wise Distance Distributions.
Graph Parameters, Implicit Representations and Factorial Properties
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
Letter graphs and geometric grid classes of permutations
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
2021
Randomized Communication and Implicit Graph Representations
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
Sliding window temporal graph coloring
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
Deleting edges to restrict the size of an epidemic in temporal networks
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
Graph classes with linear Ramsey numbers
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
Sharp Thresholds in Random Simple Temporal Graphs.
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?
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
Sharp Thresholds in Random Simple Temporal Graphs
Sharp Thresholds in Random Simple Temporal Graphs
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
Succinct Permutation Graphs
Tsakalidis, K., Wild, S., & Zamaraev, V. (2020). Succinct Permutation Graphs. Retrieved from http://dx.doi.org/10.1007/s00453-022-01039-2
Succinct Permutation Graphs
Letter graphs and geometric grid classes of permutations: Characterization and recognition
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
Letter graphs and geometric grid classes of permutations: Characterization and recognition.
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
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
Matching in Stochastically Evolving Graphs
Matching in Stochastically Evolving Graphs
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
Clique-Width for Graph Classes Closed under Complementation
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
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
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
Independent domination versus weighted independent domination.
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
Temporal Vertex Cover with a Sliding Time Window
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
Computing Maximum Matchings in Temporal Graphs.
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
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle.
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
2019
Graph classes with linear Ramsey numbers
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
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
INDEPENDENT TRANSVERSALS VERSUS TRANSVERSALS
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/
Computing Maximum Matchings in Temporal Graphs
Computing Maximum Matchings in Temporal Graphs
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
How fast can we reach a target vertex in stochastic temporal graphs?
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?
Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks.
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.
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
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
2018
Sliding Window Temporal Graph Coloring
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/
Sliding Window Temporal Graph Coloring
Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
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
Linear read-once and related Boolean functions
Linear read-once and related Boolean functions
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
Deleting edges to restrict the size of an epidemic in temporal networks
Deleting edges to restrict the size of an epidemic in temporal networks
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
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Konrad, C., & Zamaraev, V. (2018). Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. Retrieved from http://arxiv.org/abs/1805.04544v1
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Well-quasi-ordering versus clique-width
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
Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
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
Letter graphs and geometric grid classes of permutations: characterization and recognition
Temporal Vertex Cover with a Sliding Time Window
Temporal Vertex Cover with a Sliding Time Window
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.
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
Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
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
Linear Clique-Width of Bi-complement Reducible Graphs
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
Linear Ramsey Numbers
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
Linear read-once and related Boolean functions.
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
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
Specifying a positive threshold function via extremal points
Specifying a positive threshold function via extremal points
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
Clique-Width for Graph Classes Closed under Complementation
Clique-Width for Graph Classes Closed under Complementation
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
Infinitely many minimal classes of graphs of unbounded clique-width
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
Clique-Width for Graph Classes Closed under Complementation.
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
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
Specifying a positive threshold function via extremal points.
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
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
Upper Domination: towards a dichotomy through boundary properties
The structure and the number of $P_7$-free bipartite graphs
The structure and the number of <i>P</i><sub>7</sub>-free bipartite graphs
Lozin, V., & Zamaraev, V. (2017). The structure and the number of <i>P</i><sub>7</sub>-free bipartite graphs. EUROPEAN JOURNAL OF COMBINATORICS, 65, 143-153. doi:10.1016/j.ejc.2017.05.008
More results on weighted independent domination
More results on weighted independent domination
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
On Forbidden Induced Subgraphs for Unit Disk Graphs
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
On forbidden induced subgraphs for unit disk graphs
A Boundary Property for Upper Domination
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
2015
Dominating induced matchings in graphs containing no long claw
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
Well-quasi-ordering Does Not Imply Bounded Clique-width
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
Well-quasi-ordering does not imply bounded clique-width
Boundary Properties of Factorial Classes of Graphs
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
A tolerance-based heuristic approach for the weighted independent set problem
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
Well-quasi-ordering Does Not Imply Bounded Clique-width.
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
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
Combinatorics and algorithms for augmenting graphs
Implicit representations and factorial properties of graphs
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
Market Graph and Markowitz Model
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
Locally bounded coverings and factorial properties of graphs (vol 33, pg 534, 2012)
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
Network Structures Uncertainty for Different Markets
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
Social Networks and the Economics of Sports
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
The Impact of Social Networks on Sports
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
2013
Measures of uncertainty in market network analysis
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
2012
On factorial properties of chordal bipartite graphs
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
Locally bounded coverings and factorial properties of graphs
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
2011
On estimation of the number of graphs in some hereditary classes
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
A note on the speed of hereditary graph properties
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
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.