FVF: publications in journals

2013

2013a
Distortion is fixed parameter tractable
M. R. Fellows and F. V. Fomin and D. Lokshtanov and E. Losievskaja and F. A. Rosamond and S. Saurabh
ACM Transactions on Computation Theory  5  16  (2013)
link
2013b
Quadratic upper bounds on the Erdos-Pósa property for a generalization of packing and covering cycles
F. V. Fomin and D. Lokshtanov and N. Misra and G. Philip and S. Saurabh
Journal of Graph Theory  74  417-424  (2013)
link
2013c
Exact exponential algorithms
F. V. Fomin and P. Kaski
Commun. ACM  56  80-88  (2013)
link
2013d
Subexponential parameterized algorithm for minimum fill-in
F. V. Fomin and Y. Villanger
SIAM J. Comput.  42  2197--2216  (2013)
link
2013e
A Polynomial kernel for proper interval vertex deletion
F. V. Fomin and S. Saurabh and Y. Villanger
SIAM J. Discrete Math.  27  1964--1976  (2013)
link
2013f
Computing optimal Steiner trees in polynomial space
F. V. Fomin and F. Grandoni and D. Kratsch and D. Lokshtanov and S. Saurabh
Algorithmica  65  584--604  (2013)
link
2013g
Exact algorithms for finding longest cycles in claw-free graphs
H. Broersma and F. V. Fomin and P. van 't Hof and D. Paulusma
Algorithmica  65  129--145  (2013)
link
2013h
Three complexity results on coloring $P_k$-free graphs
H. Broersma and F. V. Fomin and P. A. Golovach and D. Paulusma
European J. Combin.  34  609--619  (2013)
link
2013i
A linear vertex kernel for maximum internal spanning tree
F. V. Fomin and S. Gaspers and S. Saurabh and S. Thomassé
J. Comput. System Sci.  79  1--6  (2013)
link

2012

2012a
A note on exact algorithms for vertex ordering problems on graphs
H. L. Bodlaender and F. V. Fomin and A. M. C. A. Koster and D. Kratsch and D. M. Thilikos
Theory Comput. Syst.  50  420--432  (2012)
link
2012b
Catalan structures and dynamic programming in H-minor-free graphs
F. Dorn and F. V. Fomin and D. M. Thilikos
J. Comput. System Sci.  78  1606--1622  (2012)
link
2012c
Connected graph searching
L. Barrière and P. Flocchini and F. V. Fomin and P. Fraigniaud and N. Nisse and N. Santoro and D. M. Thilikos
Inform. and Comput.  219  1--16  (2012)
link
2012d
Cops and robber game without recharging
F. V. Fomin and P. A. Golovach and D. Lokshtanov
Theory Comput. Syst.  50  611--620  (2012)
link
2012e
Cops and robber with constraints
F. V. Fomin and P. A. Golovach and P. Pralat
SIAM J. Discrete Math.  26  571-590  (2012)
link
2012f
Counting subgraphs via homomorphisms
O. Amini and F. V. Fomin and S. Saurabh
SIAM J. Discrete Math.  26  695-717  (2012)
link
2012g
Fast minor testing in planar graphs
I. Adler and F. Dorn and F. V. Fomin and I. Sau and D. M. Thilikos
Algorithmica  64  69--84  (2012)
link
2012h
Faster algorithms for finding and counting subgraphs
F. V. Fomin and D. Lokshtanov and V. Raman and S. Saurabh and B. V. R. Rao
J. Comput. System Sci.  78  698--706  (2012)
link
2012i
Kernel(s) for problems with no kernel: On out-trees with many leaves
D. Binkele-Raible and H. Fernau and F. V. Fomin and D. Lokshtanov and S. Saurabh and Y. Villanger
ACM Transactions on Algorithms  8  38  (2012)
link
2012j
Local search: is brute-force avoidable?
M. R. Fellows and F. V. Fomin and D. Lokshtanov and F. Rosamond and S. Saurabh and Y. Villanger
J. Comput. System Sci.  78  707--719  (2012)
link
2012k
On exact algorithms for treewidth
H. L. Bodlaender and F. V. Fomin and A. M. C. A. Koster and D. Kratsch and D. M. Thilikos
ACM Transactions on Algorithms  9  12  (2012)
link
2012l
Parameterized complexity of the spanning tree congestion problem
H. L. Bodlaender and F. V. Fomin and P. A. Golovach and Y. Otachi and E. J. van Leeuwen
Algorithmica  64  85--111  (2012)
link
2012m
Sharp separation and applications to exact and parameterized algorithms
F. V. Fomin and F. Grandoni and D. Lokshtanov and S. Saurabh
Algorithmica  63  692--706  (2012)
link
2012n
Treewidth computation and extremal combinatorics
F. V. Fomin and Y. Villanger
Combinatorica  32  289--308  (2012)
link

2011

2011p
Faster parameterized algorithms for minor containment
I. Adler and F. Dorn and F. V. Fomin and I. Sau and D. M. Thilikos
Theoret. Comput. Sci.  412  7018--7028  (2011)
link
2011o
How to guard a graph?
F. V. Fomin and P. A. Golovach and A. Hall and M. Mihalák and E. Vicari and P. Widmayer
Algorithmica  61  839--856  (2011)
link
2011n
Guard games on graphs: keep the intruder out!
F. V. Fomin and P. A. Golovach and D. Lokshtanov
Theoret. Comput. Sci.  412  6484--6497  (2011)
link
2011m
Approximating width parameters of hypergraphs with excluded minors
F. V. Fomin and P. A. Golovach and D. M. Thilikos
SIAM J. Discrete Math.  25  1331--1348  (2011)
link
2011l
Implicit branching and parameterized partial cover problems
O. Amini and F. V. Fomin and S. Saurabh
J. Comput. System Sci.  77  1159--1171  (2011)
link
2011k
Spanners in sparse graphs
F. F. Dragan and F. V. Fomin and P. A. Golovach
J. Comput. System Sci.  77  1108--1119  (2011)
link
2011j
Kernels for feedback arc set in tournaments
S. Bessy and F. V. Fomin and S. Gaspers and C. Paul and A. Perez and S. Saurabh and S. Thomassé
J. Comput. System Sci.  77  1071--1078  (2011)
link
2011i
On the complexity of reconstructing H-free graphs from their star systems
F. V. Fomin and J. Kratochvil and D. Lokshtanov and F. Mancini and J. A. Telle
J. Graph Theory  68  113--124  (2011)
link
2011h
Subexponential algorithms for partial cover problems
F. V. Fomin and D. Lokshtanov and V. Raman and S. Saurabh
Inform. Process. Lett.  111  814--818  (2011)
link
2011g
Branch and recharge: exact algorithms for generalized domination
F. V. Fomin and P. A. Golovach and J. Kratochvil and D. Kratsch and M. Liedloff
Algorithmica  61  252--273  (2011)
link
2011f
An exact algorithm for minimum distortion embedding
F. V. Fomin and D. Lokshtanov and S. Saurabh
Theoret. Comput. Sci.  412  3530--3536  (2011)
link
2011e
Contraction obstructions for treewidth
F. V. Fomin and P. Golovach and D. M. Thilikos
J. Combin. Theory Ser. B  101  302--314  (2011)
link
2011d
Approximation of minimum weight spanners for sparse graphs
F. F. Dragan and F. V. Fomin and P. A. Golovach
Theoret. Comput. Sci.  412  846--852  (2011)
link
2011c
Strengthening Erdős-Posa property for minor-closed graph classes
F. V. Fomin and S. Saurabh and D. M. Thilikos
J. Graph Theory  66  235--240  (2011)
link
2011b
On the complexity of some colorful problems parameterized by treewidth
M. R. Fellows and F. V. Fomin and D. Lokshtanov and F. Rosamond and S. Saurabh and S. Szeider and C. Thomassen
Inform. and Comput.  209  143--153  (2011)
link
2011a
Spanners of bounded degree graphs
F. V. Fomin and P. A. Golovach and E. J. van Leeuwen
Inform. Process. Lett.  111  142--144  (2011)
link

2010

2010h
Mixed search number and linear-width of interval and split graphs
F. V. Fomin and P. Heggernes and R. Mihai
Networks  56  207--214  (2010)
link
2010g
Rank-width and tree-width of H-minor-free graphs
F. V. Fomin and S.-i. Oum and D. M. Thilikos
European J. Combin.  31  1617--1628  (2010)
link
2010f
Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions
F. Dorn and E. Penninkx and H. L. Bodlaender and F. V. Fomin
Algorithmica  58  790--810  (2010)
link
2010e
Parameterized algorithm for eternal vertex cover
F. V. Fomin and S. Gaspers and P. A. Golovach and D. Kratsch and S. Saurabh
Inform. Process. Lett.  110  702--706  (2010)
link
2010d
Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem
N. Cohen and F. V. Fomin and G. Gutin and E. J. Kim and S. Saurabh and A. Yeo
J. Comput. System Sci.  76  650--662  (2010)
link
2010c
Pursuing a fast robber on a graph
F. V. Fomin and P. A. Golovach and J. Kratochvil and N. Nisse and K. Suchan
Theoret. Comput. Sci.  411  1167--1181  (2010)
link
2010b
Iterative compression and exact algorithms
F. V. Fomin and S. Gaspers and D. Kratsch and M. Liedloff and S. Saurabh
Theoret. Comput. Sci.  411  1045--1053  (2010)
link
2010a
Intractability of clique-width parameterizations
F. V. Fomin and P. A. Golovach and D. Lokshtanov and S. Saurabh
SIAM J. Comput.  39  1941--1956  (2010)
link

2009

2009e
A measure & conquer approach for the analysis of exact algorithms
F. V. Fomin and F. Grandoni and D. Kratsch
J. ACM  56  Art. 25, 32  (2009)
link
2009d
Computing branchwidth via efficient triangulations and blocks
F. V. Fomin and F. Mazoit and I. Todinca
Discrete Appl. Math.  157  2726--2736  (2009)
link
2009c
Sort and search: exact algorithms for generalized domination
F. V. Fomin and P. A. Golovach and J. Kratochvil and D. Kratsch and M. Liedloff
Inform. Process. Lett.  109  795--798  (2009)
link
2009b
On two techniques of combining branching and treewidth
F. V. Fomin and S. Gaspers and S. Saurabh and A. A. Stepanov
Algorithmica  54  181--207  (2009)
link
2009a
Nondeterministic graph searching: from pathwidth to treewidth
F. V. Fomin and P. Fraigniaud and N. Nisse
Algorithmica  53  358--373  (2009)
link

2008

2008h
Subexponential parameterized algorithms
F. Dorn and F. V. Fomin and D.M. Thilikos
Computer Science Review  2  29--39  (2008)
link
2008g
Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications
F. V. Fomin and F. Grandoni and A. V. Pyatkin and A. A. Stepanov
ACM Trans. Algorithms  5  Art. 9, 17  (2008)
link
2008f
Spanning directed trees with many leaves
N. Alon and F. V. Fomin and G. Gutin and M. Krivelevich and S. Saurabh
SIAM J. Discrete Math.  23  466--476  (2008/09)
link
2008e
Improved algorithms for feedback vertex set problems
J. Chen and F. V. Fomin and Y. Liu and S. Lu and Y. Villanger
J. Comput. System Sci.  74  1188--1198  (2008)
link
2008d
On the minimum feedback vertex set problem: exact and enumeration algorithms
F. V. Fomin and S. Gaspers and A. V. Pyatkin and I. Razgon
Algorithmica  52  293--307  (2008)
link
2008c
Solving connected dominating set faster than {2^n}
F. V. Fomin and F. Grandoni and D. Kratsch
Algorithmica  52  153--166  (2008)
link
2008b
Exact algorithms for treewidth and minimum fill-in
F. V. Fomin and D. Kratsch and I. Todinca and Y. Villanger
SIAM J. Comput.  38  1058--1079  (2008)
link
2008a
An annotated bibliography on guaranteed graph searching
F. V. Fomin and D. M. Thilikos
Theoret. Comput. Sci.  399  236--245  (2008)
link

2007

2007d
Exact algorithms for graph homomorphisms
F. V. Fomin and P. Heggernes and D. Kratsch
Theory Comput. Syst.  41  381--393  (2007)
link
2007c
Backbone colorings for graphs: tree and path backbones
H. Broersma and F. V. Fomin and P. A. Golovach and G. J. Woeginger
J. Graph Theory  55  137--152  (2007)
link
2007b
On self duality of pathwidth in polyhedral graph embeddings
F. V. Fomin and D. M. Thilikos
J. Graph Theory  55  42--54  (2007)
link
2007a
Eliminating graphs by means of parallel knock-out schemes
H. Broersma and F. V. Fomin and R. Královic and G. J. Woeginger
Discrete Appl. Math.  155  92--102  (2007)
link

2006

2006e
A 3-approximation for the pathwidth of Halin graphs
F. V. Fomin and D. M. Thilikos
J. Discrete Algorithms  4  499--510  (2006)
link
2006d
Dominating sets in planar graphs: branch-width and exponential speed-up
F. V. Fomin and D. M. Thilikos
SIAM J. Comput.  36  281--309  (2006)
link
2006c
Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult
H. Broersma and F. V. Fomin and J. Kratochvil and G. J. Woeginger
Algorithmica  44  343--361  (2006)
link
2006b
Pathwidth of cubic graphs and exact algorithms
F. V. Fomin and K. Høie
Inform. Process. Lett.  97  191--196  (2006)
link
2006a
New upper bounds on the decomposability of planar graphs
F. V. Fomin and D. M. Thilikos
J. Graph Theory  51  53--81  (2006)
link

2005

2005g
Some new techniques in design and analysis of exact (exponential) algorithms
F. V. Fomin and F. Grandoni and D. Kratsch
Bull. Eur. Assoc. Theor. Comput. Sci. EATCS    47--77  (2005)
link
2005f
Equitable colorings of bounded treewidth graphs
H. L. Bodlaender and F. V. Fomin
Theoret. Comput. Sci.  349  22--30  (2005)
link
2005e
Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
E. D. Demaine and F. V. Fomin and M. Hajiaghayi and D. M. Thilikos
J. ACM  52  866--893  (2005)
link
2005d
Bidimensional parameters and local treewidth
E. D. Demaine and F. V. Fomin and M. Hajiaghayi and D. M. Thilikos
SIAM J. Discrete Math.  18  501--511  (2004/05)
link
2005c
Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs
E. D. Demaine and F. V. Fomin and M. Hajiaghayi and D. M. Thilikos
ACM Trans. Algorithms  1  33--47  (2005)
link
2005b
Tree decompositions with small cost
H. L. Bodlaender and F. V. Fomin
Discrete Appl. Math.  145  143--154  (2005)
link
2005a
Graph searching, elimination trees, and a generalization of bandwidth
F. V. Fomin and P. Heggernes and J. A. Telle
Algorithmica  41  73--87  (2005)
link

2004

2004f
Radio labeling with preassigned frequencies
H. L. Bodlaender and H. Broersma and F. V. Fomin and A. V. Pyatkin and G. J. Woeginger
SIAM J. Optim.  15  1--16   (2004)
link
2004e
On distance constrained labeling of disk graphs
J. Fiala and A. V. Fishkin and F. Fomin
Theoret. Comput. Sci.  326  261--292  (2004)
link
2004d
AT-free graphs: linear bounds for the oriented diameter
F. V. Fomin and M. Matamala and E. Prisner and I. Rapaport
Discrete Appl. Math.  141  135--148  (2004)
link
2004c
Searching expenditure and interval graphs
F. V. Fomin
Discrete Appl. Math.  135  97--104  (2004)
link
2004b
Complexity of approximating the oriented diameter of chordal graphs
F. V. Fomin and M. Matamala and I. Rapaport
J. Graph Theory  45  255--269  (2004)
link
2004a
Algorithms for graphs with small octopus
F. V. Fomin and D. Kratsch and H. Müller
Discrete Appl. Math.  134  105--128  (2004)
link

2003

2003d
On the monotonicity of games generated by symmetric submodular functions
F. V. Fomin and D. M. Thilikos
Discrete Appl. Math.  131  323--335  (2003)
link
2003c
Interval degree and bandwidth of a graph
F. V. Fomin and P. A. Golovach
Discrete Appl. Math.  129  345--359  (2003)
link
2003b
On the domination search number
F. V. Fomin and D. Kratsch and H. Müller
Discrete Appl. Math.  127  565--580  (2003)
link
2003a
Pathwidth of planar and line graphs
F. V. Fomin
Graphs Combin.  19  91--99  (2003)
link

2002

2002d
More about subcolorings
H. Broersma and F. V. Fomin and J. Nesetril and G. J. Woeginger
Computing  69  187--203  (2002)
link
2002c
Approximating minimum cocolorings
F. V. Fomin and D. Kratsch and J.-C. Novelli
Inform. Process. Lett.  84  285--290  (2002)
link
2002b
Approximation of pathwidth of outerplanar graphs
H. L. Bodlaender and F. V. Fomin
J. Algorithms  43  190--200  (2002)
link
2002a
Approximation algorithms for time-dependent orienteering
F. V. Fomin and A. Lingas
Inform. Process. Lett.  83  57--62  (2002)
link

2001

2001b
A generalization of the graph bandwidth
F. V. Fomin
Vestnik St. Petersburg Univ. Math.  34  15--19 (2002)  (2001)
link
2001a
The search and the node-search number of dual graphs
P. A. Golovach and F. V. Fomin
Vestn. Syktyvkar. Univ. Ser. 1 Mat. Mekh. Inform.    125--136  (2001)
link

2000

2000b
Search in graphs
P. A. Golovach and N. N. Petrov and F. V. Fomin
Proc. Steklov Inst. Math.    S90--S103  (2000)
link
2000a
Graph searching and interval completion
F. V. Fomin and P. A. Golovach
SIAM J. Discrete Math.  13  454--464   (2000)
link

1999

1999c
Discrete search programs on graphs
N. N. Petrov and F. V. Fomin
Vestnik St. Petersburg Univ. Math.  32  27--32 (2000)  (1999)
link
1999b
On a complementary interval graph with the lowest max-degree
P. A. Golovach and F. V. Fomin
Vestnik St. Petersburg Univ. Math.  32  7--10 (2000)  (1999)
link
1999a
Note on a helicopter search problem on graphs
F. V. Fomin
Discrete Appl. Math.  95  241--249  (1999)
link

1998

1998d
Search costs and interval graphs
F. V. Fomin
Diskretn. Anal. Issled. Oper. Ser. 1  5  70--79, 97  (1998)
link
1998c
The total vertex separation number and the profile of graphs
P. A. Golovach and F. V. Fomin
Diskret. Mat.  10  87--94  (1998)
link
1998b
Helicopter search problems, bandwidth and pathwidth
F. V. Fomin
Discrete Appl. Math.  85  59--70  (1998)
link
1998a
Search problems on 1-skeletons of regular polyhedrons
F. V. Fomin and P. A. Golovach and N. N. Petrov
Int. J. Math. Game Theory Algebra  7  101--111  (1998)
link

1997

1997a
Almost discrete search programs on graphs
F. V. Fomin
Vestnik St. Petersburg Univ. Math.  30  44--49 (1998)  (1997)
link

1993-1995

1995a
Search problem on trees
F. V. Fomin
Vestnik St. Petersburg Univ. Math.  28  36--39 (1996)  (1995)
link
1995b
The search for the evader on 3-minimal trees
F. V. Fomin
Vestnik St. Petersburg Univ. Math.  28  56--60 (1996)  (1995)
link
1994a
A search problem on a graph under restriction of the velocity
F. V. Fomin
Vestnik St. Petersburg Univ. Math.  27  50--54  (1994)
link

1993a
Synthesis of a discrete algorithm for the adaptive control of a linear plant by the Lyapunov function method
F. V. Fomin
Vestnik S.-Peterburg. Univ. Mat. Mekh. Astronom.    40--44, 150 (1994)  (1993)
link