Home
  • E-mailFedor.Fomin@uib.no
  • Phone+47 55 58 40 24
  • Visitor Address
    HIB - Thormøhlens gate 55
  • Postal Address
    Postboks 7803
    5020 Bergen

I am a professor in computer science at the University of Bergen, doing research in Algorithms and Combinatorics. My Master (1992) and PhD (1997) degrees are from the  Faculty of Mathematics and Mechanics, St. Petersburg State University and my supervisor was Prof. Nikolay Petrov. Here is a link to my page at the Mathematics Genealogy Project. I was an assistant professor at St. Petersburg State University (chair of  Operations Research) till 1999. I did postdocs in Chile (CMM and Universidad de Chile), Czech Republic (ITI and Charles University), and Germany (University of Paderborn). Since 2002, I am at the  Department of InformaticsUniversity of Bergen.

 

 

 

Open acess publications in arXiv.

Books (with links to free downloads)

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi, Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, 2019. Amazon link. Free downloadable version and errata are available from  here.

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015. Amazon link. Free downloadable version and errata are available from  here.

Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010. Amazon link. Free downloadable version and errata are available from  here.

 

 

The following list of publications is automatically generated (with some mistakes) from the national database CRIStin. 

 

Academic article
  • Show author(s) 2019. Spanning circuits in regular matroids. ACM Transactions on Algorithms (TALG).
  • Show author(s) 2019. Path Contraction Faster Than 2n. Leibniz International Proceedings in Informatics. 11:1-11:13.
  • Show author(s) 2019. Parameterized k-Clustering: Tractability Island. Leibniz International Proceedings in Informatics. 14:1-14:15.
  • Show author(s) 2019. Modification to planarity is fixed parameter tractable. Leibniz International Proceedings in Informatics. 28:1-28:17.
  • Show author(s) 2019. Kernelization of graph hamiltonicity: Proper H-graphs. Lecture Notes in Computer Science (LNCS). 296-310.
  • Show author(s) 2019. Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 47:1-47:14.
  • Show author(s) 2019. Decomposition of map graphs with applications. Leibniz International Proceedings in Informatics. 60:1-60:15.
  • Show author(s) 2019. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. Leibniz International Proceedings in Informatics. 59:1-59:13.
  • Show author(s) 2019. Approximation Schemes for Low-rank Binary Matrix Approximation Problems. ACM Transactions on Algorithms (TALG). 12:1-12:39.
  • Show author(s) 2018. Subexponential parameterized algorithm for interval completion. ACM Transactions on Algorithms (TALG). 62 pages.
  • Show author(s) 2018. Structured connectivity augmentation. SIAM Journal on Discrete Mathematics. 2612-2635.
  • Show author(s) 2018. Preface to Special Issue Dedicated to the 60th Birthday of Gregory Gutin. Algorithmica. 2513-2515.
  • Show author(s) 2018. Partial Complementation of Graphs. Leibniz International Proceedings in Informatics. 21:1-21:13.
  • Show author(s) 2018. Parameterized low-rank binary matrix approximation. Leibniz International Proceedings in Informatics. 1-16.
  • Show author(s) 2018. On the tractability of optimization problems on H-graphs. Leibniz International Proceedings in Informatics. 1-14.
  • Show author(s) 2018. On the optimality of pseudo-polynomial algorithms for integer programming. Leibniz International Proceedings in Informatics. 31:1-31:13.
  • Show author(s) 2018. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG).
  • Show author(s) 2018. Excluded grid minors and efficient polynomial-time approximation schemes. Journal of the ACM. 1-44.
  • Show author(s) 2018. Exact algorithms for terrain guarding. ACM Transactions on Algorithms (TALG). 20 pages.
  • Show author(s) 2018. Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 2512-2565.
  • Show author(s) 2018. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 27 pages.
  • Show author(s) 2018. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. Leibniz International Proceedings in Informatics. 21:1-21:14.
  • Show author(s) 2018. A Fixed-Parameter Perspective on #BIS. Leibniz International Proceedings in Informatics. 13:1-13:13.
  • Show author(s) 2017. Tight lower bounds on graph embedding problems. Journal of the ACM. 1-22.
  • Show author(s) 2017. Structured Connectivity Augmentation. Leibniz International Proceedings in Informatics.
  • Show author(s) 2017. Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
  • Show author(s) 2017. Representative families of product families. ACM Transactions on Algorithms (TALG). 1-29.
  • Show author(s) 2017. Metric Dimension of Bounded Tree-length Graphs. SIAM Journal on Discrete Mathematics. 1217-1243.
  • Show author(s) 2017. Matrix rigidity from the viewpoint of parameterized complexity. Leibniz International Proceedings in Informatics.
  • Show author(s) 2017. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Leibniz International Proceedings in Informatics. 1-15.
  • Show author(s) 2017. Finding detours is fixed-parameter tractable. Leibniz International Proceedings in Informatics. 1-14.
  • Show author(s) 2017. Faster exact algorithms for some terminal set problems. Journal of computer and system sciences. 195-207.
  • Show author(s) 2017. Exact algorithms for terrain guarding. Leibniz International Proceedings in Informatics. 111-1115.
  • Show author(s) 2017. Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
  • Show author(s) 2017. Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica. 1146-1169.
  • Show author(s) 2016. Vertex cover structural parameterization revisited. Lecture Notes in Computer Science (LNCS). 171-182.
  • Show author(s) 2016. The Firefighter problem on graph classes. Theoretical Computer Science. 38-50.
  • Show author(s) 2016. Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Leibniz International Proceedings in Informatics. 39.1-39.15.
  • Show author(s) 2016. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 515-524.
  • Show author(s) 2016. Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation. 11-22.
  • Show author(s) 2016. Parameterized complexity of secluded connectivity problems. Theory of Computing Systems. 1-25.
  • Show author(s) 2016. Parameterized Complexity of Superstring Problems. Algorithmica. 1-16.
  • Show author(s) 2016. Kernelization and sparseness: The case of dominating set. Leibniz International Proceedings in Informatics. 14 pages.
  • Show author(s) 2016. How to hunt an invisible rabbit on a graph. European journal of combinatorics (Print). 12-26.
  • Show author(s) 2016. Hitting forbidden minors: Approximation and kernelization. SIAM Journal on Discrete Mathematics. 383-410.
  • Show author(s) 2016. Exact algorithms via monotone local search. Proceedings of the Annual ACM Symposium on Theory of Computing. 764-775.
  • Show author(s) 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM.
  • Show author(s) 2016. Editing to connected f-degree graph. Leibniz International Proceedings in Informatics. 1-15.
  • Show author(s) 2016. A $c^k n$ 5-approximation algorithm for treewidth. SIAM journal on computing (Print). 317-378.
  • Show author(s) 2016. (Meta) Kernelization. Journal of the ACM.
  • Show author(s) 2015. Parameterized single-exponential time polynomial space algorithm for steiner tree. Lecture Notes in Computer Science (LNCS). 494-505.
  • Show author(s) 2015. Parameterized complexity of secluded connectivity problems. Leibniz International Proceedings in Informatics. 408-419.
  • Show author(s) 2015. Minimizing Rosenthal potential in multicast games. Theory of Computing Systems. 81-96.
  • Show author(s) 2015. Lower bounds for the graph homomorphism problem. Lecture Notes in Computer Science (LNCS). 481-493.
  • Show author(s) 2015. Largest chordal and interval subgraphs faster than 2n. Algorithmica. 26 pages.
  • Show author(s) 2015. Large induced subgraphs via triangulations and CMSO. SIAM journal on computing (Print). 54-87.
  • Show author(s) 2015. Graph modification problems: A modern perspective. Lecture Notes in Computer Science (LNCS). 3-6.
  • Show author(s) 2015. Exploring the subexponential complexity of completion problems. ACM Transactions on Computation Theory.
  • Show author(s) 2015. Computing tree-depth faster than 2n. Algorithmica. 202-216.
  • Show author(s) 2015. A subexponential parameterized algorithm for proper interval completion. SIAM Journal on Discrete Mathematics. 1961-1987.
  • Show author(s) 2014. To satisfy impatient Web surfers is hard. Theoretical Computer Science. 1-17.
  • Show author(s) 2014. Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. Journal of computer and system sciences. 1430-1447.
  • Show author(s) 2014. Representative sets of product families. Lecture Notes in Computer Science (LNCS). 443-454.
  • Show author(s) 2014. Parameterized complexity of firefighting. Journal of computer and system sciences. 1285-1297.
  • Show author(s) 2014. Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences. 157-179.
  • Show author(s) 2014. Parameterized algorithms to preserve connectivity. Lecture Notes in Computer Science (LNCS). 800-811.
  • Show author(s) 2014. Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 878-892.
  • Show author(s) 2014. Exploring subexponential parameterized complexity of completion problems. Leibniz International Proceedings in Informatics. 288-299.
  • Show author(s) 2014. Connecting vertices by independent trees. Leibniz International Proceedings in Informatics. 73-84.
  • Show author(s) 2014. Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.
  • Show author(s) 2014. Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Lecture Notes in Computer Science (LNCS). 182-193.
  • Show author(s) 2014. A subexponential parameterized algorithm for proper interval completion. Lecture Notes in Computer Science (LNCS). 173-184.
  • Show author(s) 2013. Tight bounds for parameterized complexity of Cluster Editing. Leibniz International Proceedings in Informatics. 32-43.
  • Show author(s) 2013. Subexponential parameterized algorithm for minimum fill-in. SIAM journal on computing (Print). 2197-2216.
  • Show author(s) 2013. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. Lecture Notes in Computer Science (LNCS). 505-516.
  • Show author(s) 2013. Quadratic upper bounds on the Erdős–Pósa property for a generalization of packing and covering cycles. Journal of Graph Theory. 417-424.
  • Show author(s) 2013. Jungles, bundles, and fixed parameter tractability. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 396-413.
  • Show author(s) 2013. Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica. 129-145.
  • Show author(s) 2013. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Information and Computation. 60-70.
  • Show author(s) 2013. An O(c^k n) 5-approximation algorithm for treewidth. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 499-508.
  • Show author(s) 2013. A polynomial kernel for proper interval vertex deletion. SIAM Journal on Discrete Mathematics. 1964-1976.
  • Show author(s) 2013. A linear vertex kernel for maximum internal spanning tree. Journal of computer and system sciences. 1-6.
  • Show author(s) 2012. k-Gap Interval Graphs. Lecture Notes in Computer Science (LNCS). 350-361.
  • Show author(s) 2012. Sharp separation and applications to exact and parameterized algorithms. Algorithmica. 692-706.
  • Show author(s) 2012. Preprocessing subgraph and minor problems: when does a small vertex cover help? Lecture Notes in Computer Science (LNCS).
  • Show author(s) 2012. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms (extended abstract). Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 470-479.
  • Show author(s) 2012. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 85-111.
  • Show author(s) 2012. On exact algorithms for treewidth. ACM Transactions on Algorithms (TALG). 23 pages.
  • Show author(s) 2012. Minimizing Rosenthal potential in multicast games. Lecture Notes in Computer Science (LNCS).
  • Show author(s) 2012. Making Life Easier for Firefighters. Lecture Notes in Computer Science (LNCS). 177-188.
  • Show author(s) 2012. Local search: Is brute-force avoidable? Journal of computer and system sciences. 707-719.
  • Show author(s) 2012. Faster algorithms for finding and counting subgraphs. Journal of computer and system sciences. 698-706.
  • Show author(s) 2012. Fast minor testing in planar graphs. Algorithmica. 69-84.
  • Show author(s) 2012. Counting subgraphs via homomorphisms. SIAM Journal on Discrete Mathematics. 695-717.
  • Show author(s) 2012. Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 571-590.
  • Show author(s) 2012. Connected graph searching. Information and Computation. 1-16.
  • Show author(s) 2012. Catalan structures and dynamic programming in H-minor-free graphs. Journal of computer and system sciences. 1606-1622.
  • Show author(s) 2012. A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems. 420-432.
  • Show author(s) 2011. Implicit branching and parameterized partial cover problems. Journal of computer and system sciences. 1159-1171.
  • Show author(s) 2011. Faster parameterized algorithms for minor containment. Theoretical Computer Science. 7018-7028.
  • Show author(s) 2011. An exact algorithm for minimum distortion embedding. Theoretical Computer Science. 3530-3536.
  • Show author(s) 2010. Protrusions in Graphs and Their Applications. Lecture Notes in Computer Science (LNCS). 3-3.
  • Show author(s) 2010. Mixed Search Number and Linear-Width of Interval and Split Graphs. Networks. 207-214.
  • Show author(s) 2010. Kernelization. Lecture Notes in Computer Science (LNCS). 107-108.
  • Show author(s) 2010. Iterative compression and exact algorithms. Theoretical Computer Science. 1045-1053.
  • Show author(s) 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
  • Show author(s) 2010. Finding Induced Subgraphs via Minimal Triangulations. Leibniz International Proceedings in Informatics. 383-394.
  • Show author(s) 2010. Faster Parameterized Algorithms for Minor Containment. Lecture Notes in Computer Science (LNCS). 322-333.
  • Show author(s) 2010. Fast exact algorithms for Hamiltonicity in claw-free graphs. Lecture Notes in Computer Science (LNCS). 44-53.
  • Show author(s) 2010. Fast Minor Testing in Planar Graphs. Lecture Notes in Computer Science (LNCS). 97-109.
  • Show author(s) 2010. Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica. 790-810.
  • Show author(s) 2010. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Leibniz International Proceedings in Informatics. 251-262.
  • Show author(s) 2010. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. Journal of computer and system sciences. 650-662.
  • Show author(s) 2009. Subexponential Algorithms for Partial Cover Problems. Leibniz International Proceedings in Informatics. 193-201.
  • Show author(s) 2009. Kernels for Feedback Arc Set In Tournaments. Leibniz International Proceedings in Informatics. 37-47.
  • Show author(s) 2009. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Leibniz International Proceedings in Informatics. 421-432.
  • Show author(s) 2009. Contraction Bidimensionality: The Accurate Picture. Lecture Notes in Computer Science (LNCS). 706-717.
  • Show author(s) 2009. Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 445-456.
  • Show author(s) 2009. An Exact Algorithm for Minimum Distortion Embedding. Lecture Notes in Computer Science (LNCS). 112-121.
  • Show author(s) 2008. Treewidth Computation and Extremal Combinatorics. Lecture Notes in Computer Science (LNCS). 210-221.
  • Show author(s) 2008. Spanners in sparse graphs. Lecture Notes in Computer Science (LNCS). 597-608.
  • Show author(s) 2008. On tractability cops and robbers game. IFIP International Federation for Information Processing. 171-185.
  • Show author(s) 2008. On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science (LNCS). 194-205.
  • Show author(s) 2008. Iterative Compression and Exact Algorithms. Lecture Notes in Computer Science (LNCS). 335-346.
  • Show author(s) 2008. Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract). Dagstuhl Seminar Proceedings. 12 pages.
  • Show author(s) 2008. How to guard a graph? Lecture Notes in Computer Science (LNCS). 318-239.
  • Show author(s) 2008. Faster Steiner Tree Computation in Polynomial-Space. Lecture Notes in Computer Science (LNCS). 430-441.
  • Show author(s) 2008. A PTAS for the sparsest spanners problem on apex-minor-free graphs. Lecture Notes in Computer Science (LNCS). 290-298.
  • Show author(s) 2007. Subexponential Parameterized Algorithms. Lecture Notes in Computer Science (LNCS). 15-27.
  • Show author(s) 2007. Parameterized Algorithms for Directed Maximum Leaf Problems. Lecture Notes in Computer Science (LNCS). 352-362.
  • Show author(s) 2007. Mixed search number and linear-width of interval and split graphs. Lecture Notes in Computer Science (LNCS). 304-315.
  • Show author(s) 2007. Improved Exact Algorithms for Counting 3- and 4-Colorings. Lecture Notes in Computer Science (LNCS). 65-74.
  • Show author(s) 2007. Improved Algorithms for the Feedback Vertex Set Problems. Lecture Notes in Computer Science (LNCS). 422-433.
  • Show author(s) 2007. Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science (LNCS). 507-518.
  • Show author(s) 2007. Better Algorithms and Bounds for Directed Maximum Leaf Problems. Lecture Notes in Computer Science (LNCS). 316-327.
  • Show author(s) 2006. Solving Connected Dominating Set Faster than O(2n). Lecture Notes in Computer Science (LNCS). 152-163.
  • Show author(s) 2006. On exact algorithms for treewidth. Lecture Notes in Computer Science (LNCS). 672-683.
  • Show author(s) 2006. Finding a Minimum Feedback Vertex Set in time O(1.7548n). Lecture Notes in Computer Science (LNCS). 184-191.
  • Show author(s) 2006. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM journal on computing (Print). 281-309.
  • Show author(s) 2006. Branching and treewidth based exact algorithms. Lecture Notes in Computer Science (LNCS). 16-25.
  • Show author(s) 2006. A 3-approximation for the pathwidth of Halin graphs. Journal of Discrete Algorithms. 499-510.
  • Show author(s) 2005. Tree decompositions with small cost. Discrete Applied Mathematics. 143-154.
  • Show author(s) 2005. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. Journal of the ACM. 866-893.
  • Show author(s) 2005. Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the European Association for Theoretical Computer Science. 47-77.
  • Show author(s) 2005. Nondeterministic Graph Searching: From Pathwidth to Treewidth. Lecture Notes in Computer Science (LNCS). 364-375.
  • Show author(s) 2005. Measure and conquer: Domination - A case study. Lecture Notes in Computer Science (LNCS). 191-203.
  • Show author(s) 2005. Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Transactions on Algorithms (TALG). 33-47.
  • Show author(s) 2005. Exact algorithms for graph homomorphisms. Lecture Notes in Computer Science (LNCS). 161-171.
  • Show author(s) 2005. Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. Lecture Notes in Computer Science (LNCS). 95-106.
  • Show author(s) 2005. Computing branchwidth via efficient triangulations and blocks. Lecture Notes in Computer Science (LNCS). 374-384.
  • Show author(s) 2005. Bounding the number of minimal dominating sets: A measure and conquer approach. Lecture Notes in Computer Science (LNCS). 573-582.
  • Show author(s) 2005. Bidimensional parameters and local treewidth. SIAM Journal on Discrete Mathematics. 501-511.
  • Show author(s) 2004. The complexity of approximating the oriented diameter of chordal graphs. Journal of Graph Theory. 255-269.
  • Show author(s) 2004. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. 823-832.
  • Show author(s) 2004. Searching expenditure and interval graphs. Discrete Applied Mathematics. 97-104.
  • Show author(s) 2004. Radio labeling with preassigned frequencies. SIAM Journal on Optimization. 1-16.
  • Show author(s) 2004. Parallel knock-out schemes in networks,. Lecture Notes in Computer Science (LNCS). 204-214.
  • Show author(s) 2004. On distance constrained labeling of disk graphs. Theoretical Computer Science. 261-292.
  • Show author(s) 2004. On distance constrained labeling of disk graphs. Theoretical Computer Science. 261-292.
  • Show author(s) 2004. Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. Lecture Notes in Computer Science (LNCS). 581-592.
  • Show author(s) 2004. Exact (exponential) algorithms for treewidth and minimum fill-in. Lecture Notes in Computer Science (LNCS). 568-580.
  • Show author(s) 2004. Exact (exponential) algorithms for the dominating set problem. Lecture Notes in Computer Science (LNCS). 245-256.
  • Show author(s) 2004. Equitable colorings of bounded treewidth graphs. Lecture Notes in Computer Science (LNCS). 180-190.
  • Show author(s) 2004. Dominating sets and local treewidth. Lecture Notes in Computer Science (LNCS). 221-229.
  • Show author(s) 2004. Bidimensional parameters and local treewidth. Lecture Notes in Computer Science (LNCS). 109-118.
  • Show author(s) 2004. Backbone colorings for networks. Lecture Notes in Computer Science (LNCS). 131-142.
  • Show author(s) 2004. Algorithms for graphs with small octopus. Discrete Applied Mathematics. 105-128.
  • Show author(s) 2004. AT-free graphs: linear bounds for the oriented diameter. Discrete Applied Mathematics. 135-148.
  • Show author(s) 2004. A simple and fast approach for solving problems on planar graphs. Lecture Notes in Computer Science (LNCS). 56-67.
  • Show author(s) 2003. Pathwidth of planar and line graphs. Graphs and Combinatorics. 91-99.
  • Show author(s) 2003. On the domination search numbe. Discrete Applied Mathematics. 565-580.
  • Show author(s) 2003. On the Monotonicity of Games Generated by Symmetric Submodular Functions. Discrete Applied Mathematics. 323-335.
  • Show author(s) 2003. Interval degree and bandwidth of a graph. Discrete Applied Mathematics. 345-359.
  • Show author(s) 2002. More About Subcolorings. Computing. 187-203.
  • Show author(s) 2002. Approximation of pathwidth of outerplanar graphs. Journal of Algorithms. 190-200.
  • Show author(s) 2002. A generalization of the graph bandwidth. Vestnik St. Petersburg Univ. Math.. 15-19.
Academic lecture
  • Show author(s) 2008. Catalan structures and dynamic programming in H-minor-free graphs.
  • Show author(s) 2004. Parallel knock-out schemes in networks.
  • Show author(s) 2004. Exact (exponential) algorithms for treewidth and minimum fill-in.
  • Show author(s) 2004. Equitable colorings of bounded treewidth graphs.
  • Show author(s) 2004. Dominating sets in planar graphs: branch-width and exponential speed-up.
  • Show author(s) 2004. Bidimensional Parameters and Local Treewidth.
  • Show author(s) 2004. A Simple and Fast Approach for Solving Problems on Planar Graphs.
  • Show author(s) 2003. Graph searching, elimination trees, and a generalization of bandwidth.
  • Show author(s) 2003. Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs.
  • Show author(s) 2003. Dominating sets and local treewidth.
  • Show author(s) 2003. Backbone colorings for networks.
  • Show author(s) 2002. Tree Decompositions with Small Cost.
  • Show author(s) 2002. Radio Labeling with Pre-assigned Frequencies.
  • Show author(s) 2001. Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.
Academic anthology/Conference proceedings
  • Show author(s) 2018. Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings. Springer.
  • Show author(s) 2012. Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings. Springer.
  • Show author(s) 2009. Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009. Springer.
  • Show author(s) 2007. Counting Minimum Weighted Dominating Sets. Springer.
  • Show author(s) 2006. Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006 Bergen, Norway, June 22-23, 2006 Revised Papers, Lecture Notes in Computer Science, vol. 4271. Springer.
Abstract
  • Show author(s) 2013. On the Parameterized Complexity of Cutting a Few Vertices from a Graph. Lecture Notes in Computer Science (LNCS). 421-432.
  • Show author(s) 2013. Long Circuits and Large Euler Subgraphs. Lecture Notes in Computer Science (LNCS). 493-504.
  • Show author(s) 2008. 08431 Executive Summary -- Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings. 3 pages.
Academic literature review
  • Show author(s) 2013. Exact exponential algorithms. Communications of the ACM. 80-88.
  • Show author(s) 2012. Kernelization algorithms (keynote speech). Smart Innovation, Systems and Technologies. 1-7.

More information in national current research information system (CRIStin)