Publications

Journal Publications

32. Succinct Permutation Graphs
    Algorithmica. 2022. (accepted) (with Tsakalidis K., Wild S.)
31. Letter graphs and geometric grid classes of permutations
    SIAM Journal on Discrete Mathematics. 2022. (accepted) (with Alecu B., Ferguson R., Kanté M.M., Lozin V., Vatter V.)
30. On Boolean threshold functions with minimum specification number
    Information and Computation. 2022. (accepted) (with Lozin V., Zamaraeva E., Zolotykh N.Yu.)
29. Distributed minimum vertex coloring and maximum independent set in chordal graphs
    Theoretical Computer Science. 2022. Vol. 922. (with Konrad C.)
28. Sliding window temporal graph coloring
    Journal of Computer and System Sciences. 2021. Vol. 120. (with Mertzios G.B., Molter H.)
27. Deleting edges to restrict the size of an epidemic in temporal networks
    Journal of Computer and System Sciences. 2021. Vol. 119. (with Enright J., Meeks K., Mertzios G.B.)
26. Graph classes with linear Ramsey numbers
    Discrete Mathematics. 2021. Vol. 344. No. 4. (with Alecu B., Atminas A., Lozin V.V.)
25. Clique-width for graph classes closed under complementation
    SIAM Journal on Discrete Mathematics. 2020. Vol. 34(2). (with Blanché A., Dabrowski K., Johnson M., Lozin V.V., Paulusma D.)
24. How fast can we reach a target vertex in stochastic temporal graphs?
    Journal of Computer and System Sciences. 2020. Vol. 114. (with Akrida E.C., Mertzios G.B., Nikoletseas S., Raptopoulos C., Spirakis P.G.)
23. Between clique-width and linear clique-width of bipartite graphs
    Discrete Mathematics. 2020. Vol. 343. No. 8 (with Alecu B., Kanté M.M., Lozin V.V.)
22. Independent domination versus weighted independent domination
    Information Processing Letters. 2020. Vol. 156. (with Lozin V.V., Malyshev D.S., Mosca R.)
21. Letter graphs and geometric grid classes of permutations: characterization and recognition
    Discrete Applied Mathematics. 2020. Vol. 283. (with Alecu B., Lozin V.V., de Werra D.)
20. Temporal vertex cover with a sliding time window
    Journal of Computer and System Sciences. 2020. Vol. 107. P. 108–123 (with Akrida E.C., Mertzios G.B., Spirakis P.G.)
19. Dominating induced matchings in graphs containing no long claw
    Journal of Graph Theory. 2018. Vol. 88. No. 1. P. 18–39. (with Hertz A., Lozin V.V., Ries B., de Werra D.)
18. Infinitely many minimal classes of graphs of unbounded clique-width
    Discrete Applied Mathematics. 2018. Vol. 248. P. 145–152. (with Collins A., Foniok J., Korpelainen N., Lozin V.V.)
17. Linear read-once and related Boolean functions
    Discrete Applied Mathematics. 2018. Vol. 250. P. 16–27. (with Lozin V.V., Razgon I., Zamaraeva E., Zolotykh N.Yu.)
16. On forbidden induced subgraphs for unit disk graphs
    Discrete & Computational Geometry. 2018. Vol. 60. No. 1. P. 57–97. (with Atminas A.)
15. Upper Domination: towards a dichotomy through boundary properties
    Algorithmica. 2018. Vol. 80. No. 10. P. 2799–2817. (with AbouEisha H., Hussain S., Lozin V.V., Monnot J., Ries B.)
14. Well-quasi-ordering versus clique-width
    Journal of Combinatorial Theory, Series B. 2018. Vol. 130. P. 1–18. (with Lozin V.V., Razgon I.)
13. More results on weighted independent domination
    Theoretical Computer Science. 2017. Vol. 700. P. 63–74. (with Lozin V.V., Malyshev D.S., Mosca R.)
12. The structure and the number of P₇-free bipartite graphs
    European Journal of Combinatorics. 2017. Vol. 65. P. 143–153. (with Lozin V.V.)
11. Combinatorics and algorithms for augmenting graphs
    Graphs and Combinatorics. 2016. Vol. 32. No. 4. P. 1339–1352. (with Dabrowski K., Lozin V.V., de Werra D.)
10. A tolerance-based heuristic approach for the weighted independent set problem
    Journal of Combinatorial Optimization. 2015. Vol. 29. No. 2. P. 433–450. (with Malyshev D.S., Pardalos P.M., et al.)
9. Boundary properties of factorial classes of graphs
   Journal of Graph Theory. 2015. Vol. 78. No. 3. P. 207–218. (with Lozin V.V.)
8. Implicit representations and factorial properties of graphs
   Discrete Mathematics. 2015. Vol. 338. No. 2. P. 164–179. (with Atminas A., Collins A., Lozin V.V.)
7. Measures of uncertainty in market network analysis
   Physica A: Statistical Mechanics and its Applications. 2014. Vol. 413. No. 1. P. 59–70. (with Kalyagin V.A., Koldanov A.P., Koldanov P.A., Pardalos P.M.)
6. On factorial subclasses of claw-free graphs
   Discrete Anal. Oper. Res.. 2013. Vol. 20. No. 6. P. 30–39. (In Russian)
5. Locally bounded coverings and factorial properties of graphs
   European Journal of Combinatorics. 2012. Vol. 33. No. 4. P. 534–543. (with Lozin V.V., Mayhill C.)
4. On factorial properties of chordal bipartite graphs
   Discrete Mathematics. 2012. Vol. 312. No. 16. P. 2457–2465. (with Dabrowski K., Lozin V.V.)
3. A note on the speed of hereditary graph properties
   Electronic Journal of Combinatorics. 2011. Vol. 18. No. 1. P. 1–14. (with Lozin V.V., Mayhill C.)
2. Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph
   Moscow Journal of Combinatorics and Number Theory. 2011. Vol. 1. No. 3. P. 277–286.
1. On estimation of the number of graphs in some hereditary classes
   Diskretn. Mat.. 2011. Vol. 23. No. 3. P. 57–62. (In Russian)

Conference Publications

23. Randomized communication and implicit graph representations
    STOC 2022 (with Harms N., Wild S.)
22. Graph Parameters, Implicit Representations and Factorial Properties
    IWOCA 2022 (with Alecu B., Alekseev V.E., Atminas A., Lozin V.)
21. Faster Exploration of Some Temporal Graphs
    SAND 2022 (with Adamson D., Gusev V.V., Malyshev D.)
20. Sharp thresholds in random simple temporal graphs
    FOCS 2021 (with Casteigts A., Raskin M., Renken M.)
19. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
    MFCS 2020 (with Deligkas A., Mertzios G.B., Spirakis P.G.)
18. Computing Maximum Matchings in Temporal Graphs
    STACS 2020 (with Mertzios G.B., Molter H., Niedermeier R., Zschoche P.)
17. Deleting edges to restrict the size of an epidemic in temporal networks
    MFCS 2019 (with Enright J., Meeks K., Mertzios G.B.)
16. Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
    MFCS 2019 (with Konrad C.)
15. How fast can we reach a target vertex in stochastic temporal graphs?
    ICALP 2019 (with Akrida E.C., Mertzios G.B., Nikoletseas S., Raptopoulos C., Spirakis P.G.)
14. Independent Transversals versus Transversals
    EuroComb 2019 (with Dabrowski K., Johnson M., Paesani G., Paulusma D.)
13. Sliding window temporal graph coloring
    AAAI 2019 (with Mertzios G.B., Molter H.)
12. Brief Ann.: Distributed Minimum Vertex Coloring and Maximum Independent Set in chordal graphs
    PODC 2018 (with 2018)
11. Linear Ramsey numbers
    IWOCA 2018 (with Atminas A., Lozin V.V.)
10. Linear clique-width of bi-complement reducible graphs
    IWOCA 2018 (with Alecu B., Lozin V.V.)
9. On the price of independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
   MFCS 2018 (with Dabrowski K., Johnson M., Paesani G., Paulusma D.)
8. Temporal vertex cover with a sliding time window
   ICALP 2018 (with Akrida E.C., Mertzios G.B., Spirakis P.G.)
7. Clique-width for graph classes closed under complementation
   MFCS 2017 (with Blanché A., Dabrowski K., Johnson M., Lozin V.V., Paulusma D.)
6. Letter graphs and geometric grid classes of permutations: characterization and recognition
   IWOCA 2017 (with Alecu B., Lozin V.V., de Werra D.)
5. New Results on Weighted Independent Domination
   WG 2017 (with Lozin V.V., Malyshev D.S., Mosca R.)
4. Specifying a positive threshold function via extremal points
   ALT 2017 (with Lozin V.V., Razgon I., Zamaraeva E., Zolotykh N.Yu.)
3. The structure and the number of P₇-free bipartite graphs
   EuroComb 2017 (with Lozin V.V.)
2. A boundary property for upper domination
   IWOCA 2016 (with AbouEisha H., Hussain S., Lozin V.V., Monnot J., Ries B.)
1. Well-quasi-ordering does not imply bounded clique-width
   WG 2015 (with Lozin V.V., Razgon I.)