Fedor V. Fomin

Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Journal of the ACM (JACM), Journal of the ACM 52 (6), (2005), pp. 866-893

A measure & conquer approach for the analysis of exact algorithms

Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch
Journal of the ACM (JACM), 56 (5), (2009) article No. 25

[Top of page]

Publications by topics

Exact (exponential) algorithms

• Fedor V. Fomin and Yngve Villanger, Finding Induced Subgraphs via Minimal Triangulations (STACS 2010)
• Omid Amini, Fedor V. Fomin, and Saket Saurabh, Counting subgraphs via homomorphisms (ICALP 2009)
• Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh, An exact algorithm for minimum distortion embedding (WG 2009, Theor. Comp. Sci 2011)
• Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov, On Two Techniques of Combining Branching and Treewidth (Algorithmica 2008)
• Fedor V. Fomin, Igor Razgon, Serge Gaspers, and Artem V. Pyatkin, On the minimum feedback vertex set problem: Exact and enumeration algorithms (Algorithmica 2008)
• Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, and Alexey A. Stepanov, Combinatorial Bounds via Measure and Conquer: Bounding Minimal Dominating Sets and Applications (ACM Transactions Algorithms 2008)
• Fedor V. Fomin and Kjartan Høie, Pathwidth of cubic graphs and exact algorithms, (Inform. Proc. Letters 2006)
• Hans L.Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch , and Dimitrios M. Thilikos, On exact algorithms for treewidth (ESA 2006)
• Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos, Fast subexponential algorithm for non-local problems on graphs of bounded genus (SWAT 2006)
• Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch , A Measure & Conquer Approach for the Analysis of Exact Algorithms (J. ACM 2009)
• Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch , Some new techniques in design and analysis of exact (exponential) algorithms (Bulletin of EATCS 87, 2005)
• Frederic Dorn, Eelko Penninkx, Hans L.Bodlaender, Fedor V. Fomin, Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions (ESA 2005)
• Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch , Exact Algorithms for Graph Homomorphisms (Theory of Comp. Syst. 2007)
• Fedor V. Fomin, Frederic Mazoit, and Ioan Todinca, Computing branchwidth via efficient triangulations and blocks (Discr. Appl. Math.)
• Fedor V. Fomin, Ioan Todinca, Dieter Kratsch , and Yngve Villanger, Exact algorithms for treewidth and minimum fill-in (SIAM J. Comp. 2008)
• Fedor V. Fomin and Yngve Villanger, Treewidth computation and extremal combinatorics (ICALP 2008)

[Top of page]

• Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh, Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments (AAAI 2010)
• Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh, Subexponential Algorithms for Partial Cover Problems (FSTTCS 2009, IPL 2011)
• Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, Yngve Villanger, Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves (STACS 2009)
• Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach, Spanners in Sparse Graphs (ICALP 2008)
• Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos, Catalan Structures and Dynamic Programming in H-minor-free graphs (SODA 2008)
• Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos, Subexponential parameterized algorithms (survey) (Computer Science Reviews 2008)
• Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, and Saket Saurabh, Spanning directed trees with many leaves , (SIAM J. Discr. Math. 2009)
• Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger, Improved Algorithms for the Feedback Vertex Set Problems, (Journal of Computer and System Sciences 2008)
• Fedor V. Fomin, Dimitrios M. Thilikos, A Simple and Fast Approach for Solving Problems on Planar Graphs , (J. Graph Theory 2006)
• Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos, Bidimensional Parameters and Local Treewidth , (SIAM J. Discr. Math. 2004)
• Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos, Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs , (J. of ACM 2005)
• Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos, Fixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs (ACM Trans. Algorithms 2005)
• Fedor V. Fomin, Dimitrios M. Thilikos, Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up (SIAM J. Computing 2006)

[Top of page]

• Hans L. Bodlaender, Fedor V. Fomin, Equitable colorings of bounded treewidth graphs , (Theor. Comp. Sci. 2005)
• Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, and Gerhard J. Woeginger, Backbone colorings for networks , (J. Graph Theory 2006)
• Hans L. Bodlaender, Hajo Broersma, Fedor V. Fomin, Artem V. Pyatkin, and Gerhard J. Woeginger , Radio labeling with pre-assigned frequencies , (SIAM J. Optim. 2004)
• Hajo Broersma, Fedor V. Fomin, Jaroslav Nesetril, and Gerhard J. Woeginger , More about subcolorings , (Computing 2003)
• Hajo Broersma, Fedor V. Fomin, Jan Kratochvil and Gerhard J. Woeginger , Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous , (Algorithmica 2006)
• Jiri Fiala , Alexei V. Fishkin and Fedor V. Fomin, On-line and off-line distance constrained labeling of disk graphs (Theor. Comp. Sci. 2004)
• Fedor V. Fomin, Dieter Kratsch and Jean-Christophe Novelli , Approximating minimum cocolourings (Inform. Proc. Letters 2002)

[Top of page]

• Fedor V. Fomin, Dimitrios Thilikos, An annotated bibliography on guaranteed graph searching (Theor. Comp. Science 2008)
• Fedor V. Fomin, Petr A. Golovach, and Daniel Lokshtanov, Cops and Robber game without recharging (SWAT 2010, Theor. of Comp. Syst. 2011)
• Fedor V. Fomin, Petr A. Golovach, Jan Kratochvi, Nicolas Nisse, and Karol Suchan, Pursuing a fast robber on a graph (Theor. Comp. Science 2010)
• Fedor V. Fomin, Petr A. Golovach, Alex Hall, Matus Mihalak, Elias Vicari, and Peter Widmayer, How to Guard a Graph? (Algorithmica 2010),
• Fedor V. Fomin, Pinar Heggernes , and Rodica Mihai, Mixed search number and linear-width of interval and split graphs , (Networks 2010)
• Fedor V. Fomin, Pierre Fraigniaud, and Nicolas Nisse , Nondeterministic Graph Searching: From Pathwidth to Treewidth, (Algorithmica 2009)
• Fedor V. Fomin, Pinar Heggernes , and Jan Arne Telle , Graph searching, elimination trees, and a generalization of bandwidth, (Algorithmica 2005)
• Fedor V. Fomin, Dieter Kratsch and Haiko Müller , On the domination search number , (Discr. Appl. Math. 2003)
• Fedor V. Fomin, Dimitrios Thilikos, On the Monotonicity of Games Generated by Symmetric Submodular Functions. (Discr. Appl. Math. 2002)
• Fedor V. Fomin and Petr A. Golovach, Interval completion and graph searching , (SIAM J. Discr. Math. 2000)
• Fedor V. Fomin, Petr A. Golovach, and Nikolai N. Petrov Search problems on 1-skeletons of regular polyhedrons (Int. J. Math., Game Theory and Algebra 1997)
• Fedor V. Fomin, Note on a helicopter search problem (Disc. Appl. Math. 1999)
• Fedor V. Fomin, Helicopter search problems, bandwidth and pathwidth (Disc. Appl. Math. 1998)

[Top of page]

• Fedor V. Fomin, Petr Golovach, Dimitrios Thilikos, Approximating Acyclicity Parameters of Sparse Hypergraphs (STACS 2009)
• Fedor V. Fomin, Dimitrios Thilikos, A 3-approximation for the pathwidth of Halin graphs (J. Discr. Algorithms 2006)
• Hans L. Bodlaender, Fedor V. Fomin, Tree decompositions with small cost (Discr. Appl. Math. 2005)
• Fedor V. Fomin, Dieter Kratsch and Haiko Müller , Algorithms for graphs with small octopus (Discr. Appl. Math. 2004)
• Hans L. Bodlaender and Fedor V. Fomin, Approximation of pathwidth of outerplanar graphs. (J. of Algorithms 2002)
• Fedor V. Fomin and Petr  A. Golovach, Interval degree and bandwidth of a graph , (Discr. Appl. Math. 2003)
• Fedor V. Fomin, Pathwidth of planar and line graphs, (Graphs and Combinatorics, 2002)

[Top of page]

• Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Dieter Kratsch, and Saket Saurabh, Parameterized Algorithm for Eternal Vertex Cover , (IPL 2010)
• Fedor V. Fomin, Jan Kratochvil, Daniel Lokshtanov, Federico Mancini, and Jan Arne Telle, On the Complexity of Reconstructing H-free Graphs from their Star Systems , (LATIN 2008, J. Graph Theory 2011)
• Johanne Cohen, Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch , and Gregory Kucherov Optimal linear arrangement of interval graphs, (MFCS 2006)
• Hajo Broersma, Fedor V. Fomin, and Gerhard J. Woeginger, Parallel knock-out schemes in networks , (Discr. Appl. Math. 2006)
• Fedor V. Fomin, Martin Matamala and Ivan Rapaport, The complexity of approximating the oriented diameter of chordal graphs. (J. Graph Theory 2004)
• Fedor V. Fomin, Martin Matamala, Erich Prisner, and Ivan Rapaport, Bilateral Orientations and Domination. (Discr. Appl. Math. 2004)
• Fedor V. Fomin, Andrzej Lingas, Approximation algorithms for time time-dependent orienteering, (Inform. Proc. Letters 2002)

[Top of page]

• Coauthor Index by DBLP

[Top of page]