Dr Viktor Zamaraev

Computer Science

    Publications

    2020

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

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

    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

    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

    Computing Maximum Matchings in Temporal Graphs (Journal article)

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

    DOI: 10.4230/LIPIcs.STACS.2020.27

    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

    2019

    Graph classes with linear Ramsey numbers (Journal article)

    Alecu, B., Atminas, A., Lozin, V., & Zamaraev, V. (n.d.). Graph classes with linear Ramsey numbers. Retrieved from http://arxiv.org/abs/1910.12109v2

    Independent transversals versus transversals (Journal article)

    Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). Independent transversals versus transversals. Acta Mathematica Universitatis Comenianae, 88(3), 585-591.

    Temporal vertex cover with a sliding time window. (Journal article)

    Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window.. J. Comput. Syst. Sci., 107, 108-123.

    Linear Programming complementation and its application to fractional graph theory (Journal article)

    Gadouleau, M., Mertzios, G. B., & Zamaraev, V. (n.d.). Linear Programming complementation and its application to fractional graph theory. Retrieved from http://arxiv.org/abs/1907.12775v1

    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. (n.d.). How fast can we reach a target vertex in stochastic temporal graphs?. Retrieved from http://arxiv.org/abs/1903.03636v1

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

    Enright, J., Meeks, K., Mertzios, G. B., & Zamaraev, V. (2019). Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks.. In MFCS (pp. 57:1).

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

    Akrida, E. C., Mertzios, G. B., Nikoletseas, S. E., Raptopoulos, C. L., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. CoRR, abs/1903.03636.

    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. (2019). On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal.. CoRR, abs/1910.05254.

    Sliding Window Temporal Graph Coloring (Journal article)

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

    2018

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

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

    Temporal vertex cover with a sliding time window (Conference Paper)

    Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zarnaraev, V. (2020). Temporal vertex cover with a sliding time window. In JOURNAL OF COMPUTER AND SYSTEM SCIENCES Vol. 107 (pp. 108-123). doi:10.1016/j.jcss.2019.08.002

    DOI: 10.1016/j.jcss.2019.08.002

    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

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

    Konrad, C., Zamaraev, V., & Machinery, A. C. (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

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

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

    Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs (Journal article)

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

    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.. Journal of Graph Theory, 88, 18-39.

    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

    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. Elsevier BV. doi:10.1016/j.dam.2020.01.038

    DOI: 10.1016/j.dam.2020.01.038

    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., 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. (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.

    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. (n.d.). On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. Retrieved from http://arxiv.org/abs/1910.05254v1

    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

    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

    2017

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

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

    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 fuer Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-046-0

    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

    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

    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 (Journal article)

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

    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/

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

    Lozin, V., & Zamaraev, V. (2017). The structure and the number of P-7-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

    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

    2016

    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

    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

    2015

    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

    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

    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

    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

    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. (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

    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

    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 (pp. 181-197). Springer International Publishing. 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)

    Social Networks and the Economics of Sports (2014). . 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

    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 http://gateway.webofknowledge.com/