FVF: publications in journals
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