Fedor Fomin's picture
Fedor
Fomin
Professor
Visit Address: 
HIB - Thormøhlensgt. 55
5020 Bergen
Postal Address: 
Postboks 7803
5020 Bergen
Phone: 
+47 55 58 40 24
Download vCard
Books
  • Fomin, Fedor; Kaski, Petteri. 2012. Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings. Springer. 397 pages. ISBN: 978-3-642-31154-3.
  • Fomin, Fedor; Kratsch, Dieter. 2010. Exact exponential algorithms. Springer. 204 pages. ISBN: 978-3-642-16532-0.
  • Chen, Jianer; Fomin, Fedor. 2009. Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009. Springer. 210 pages. ISBN: 978-3-642-11268-3.
  • Fomin, Fedor; Stepanov, Alexey. 2007. Counting Minimum Weighted Dominating Sets. Springer. 11 pages. ISBN: 3-540-73544-5.
  • Fomin, Fedor. 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. 355 pages. ISBN: 3-540-48381-0.
Journal articles
  • Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor; van Leeuwen, Erik Jan. 2014. Parameterized complexity of firefighting. Journal of computer and system sciences (Print). 80: 1285-1297. doi: 10.1016/j.jcss.2014.03.001
  • Fomin, Fedor; Giroire, Frédéric; Jean-Marie, Alain; Mazauric, Dorian; Nisse, Nicolas. 2014. To satisfy impatient Web surfers is hard. Theoretical Computer Science. 526: 1-17. doi: 10.1016/j.tcs.2014.01.009
  • Fomin, Fedor; Golovach, Petr. 2014. Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences (Print). 80: 157-179. doi: 10.1016/j.jcss.2013.07.002
  • Fomin, Fedor; Golovach, Petr. 2014. Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 28: 878-892. doi: 10.1137/130936816
  • Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve. 2014. Enumerating minimal subset feedback vertex sets. Algorithmica. 69: 216-231. doi: 10.1007/s00453-012-9731-6
  • Fomin, Fedor; Jansen, Bart Maarten Paul; Pilipczuk, Michal Pawel. 2014. Preprocessing subgraph and minor problems: When does a small vertex cover help? Journal of computer and system sciences (Print). 80: 468-495. doi: 10.1016/j.jcss.2013.09.004
  • Fomin, Fedor; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Villanger, Yngve. 2014. Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. Journal of computer and system sciences (Print). 80: 1430-1447. doi: 10.1016/j.jcss.2014.04.015
  • Fomin, Fedor; Villanger, Yngve. 2014. Searching for better fill-in. Journal of computer and system sciences (Print). 80: 1374-1383. doi: 10.1016/j.jcss.2014.04.010
  • Blizniets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve. 2013. Largest chordal and interval subgraphs faster than 2^n. Lecture Notes in Computer Science. 8125: 193-204.
  • Bodlaender, Hans L.; Drange, Pål Grønås; Dregi, Markus Sortland; Fomin, Fedor; Lokshtanov, Daniel; Pilipczuk, Michal Pawel. 2013. An O(c^k n) 5-approximation algorithm for treewidth. Symposium on Foundations of Computer Science. Annual Proceedings. 54: 499-508. doi: 10.1109/FOCS.2013.60
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Paulusma, Daniël. 2013. Three complexity results on coloring Pk-free graphs. European journal of combinatorics (Print). 34: 609-619. doi: 10.1016/j.ejc.2011.12.008
  • Broersma, Hajo; Fomin, Fedor; van 't Hof, Pim; Paulusma, Daniel. 2013. Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica. 65: 129-145. doi: 10.1007/s00453-011-9576-4
  • Dorn, Frederic; Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2013. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Information and Computation. 233: 60-70. doi: 10.1016/j.ic.2013.11.006
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket; Thomasse, Stephane. 2013. A linear vertex kernel for maximum internal spanning tree. Journal of computer and system sciences (Print). 79: 1-6. doi: 10.1016/j.jcss.2012.03.004
  • Fomin, Fedor; Giannopoulou, Archontia; Pilipczuk, Michal Pawel. 2013. Computing tree-depth faster than 2^n. Lecture Notes in Computer Science. 8246: 137-149.
  • Fomin, Fedor; Golovach, Petr. 2013. Long Circuits and Large Euler Subgraphs. Lecture Notes in Computer Science. 8125: 493-504.
  • Fomin, Fedor; Golovach, Petr; Korhonen, Janne. 2013. On the Parameterized Complexity of Cutting a Few Vertices from a Graph. Lecture Notes in Computer Science. 8087: 421-432.
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter; Lokshtanov, Daniel; Saurabh, Saket. 2013. Computing optimal Steiner trees in polynomial space. Algorithmica. 65: 584-604. doi: 10.1007/s00453-012-9612-z
  • Fomin, Fedor; Kaski, Petteri. 2013. Exact exponential algorithms. Communications of the ACM. 56: 80-88. doi: 10.1145/2428556.2428575
  • Fomin, Fedor; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Villanger, Yngve. 2013. Tight bounds for parameterized complexity of Cluster Editing. Leibniz International Proceedings in Informatics. 20: 32-43. doi: 10.4230/LIPIcs.STACS.2013.32
  • Fomin, Fedor; Lokshtanov, Daniel; Misra, Neeldhara; Philip, Geevarghese; Saurabh, Saket. 2013. Quadratic upper bounds on the Erdős–Pósa property for a generalization of packing and covering cycles. Journal of Graph Theory. 74: 417-424. doi: 10.1002/jgt.21720
  • Fomin, Fedor; Pilipczuk, Michal Pawel. 2013. Jungles, bundles, and fixed parameter tractability. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 396-413.
  • Fomin, Fedor; Pilipczuk, Michal Pawel. 2013. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. Lecture Notes in Computer Science. 8125: 505-516.
  • Fomin, Fedor; Saurabh, Saket; Villanger, Yngve. 2013. A polynomial kernel for proper interval vertex deletion. SIAM Journal on Discrete Mathematics. 27: 1964-1976. doi: 10.1137/12089051X
  • Fomin, Fedor; Villanger, Yngve. 2013. Subexponential parameterized algorithm for minimum fill-in. SIAM journal on computing (Print). 42: 2197-2216. doi: 10.1137/11085390X
  • Adler, Isolde Marianne; Dorn, Frederic; Fomin, Fedor; Sau, Ignasi; Thilikos, Dimitrios M. 2012. Fast minor testing in planar graphs. Algorithmica. 64: 69-84. doi: 10.1007/s00453-011-9563-9
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2012. Counting subgraphs via homomorphisms. SIAM Journal on Discrete Mathematics. 26: 695-717. doi: 10.1137/100789403
  • Barrière, Lali; Flocchini, Paola; Fomin, Fedor; Fraigniaud, Pierre; Nisse, Nicolas; Santoro, Nicola; Thilikos, Dimitrios M. 2012. Connected graph searching. Information and Computation. 219: 1-16. doi: 10.1016/j.ic.2012.08.004
  • Binkele-Raible, Daniel; Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve. 2012. Kernel(s) for Problems with no Kernel: On Out-Trees with Many Leaves. ACM Transactions on Algorithms. 8. 19 pages. doi: 10.1145/2344422.2344428
  • Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan. 2012. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 64: 85-111. doi: 10.1007/s00453-011-9565-7
  • Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. 2012. A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems. 50: 420-432. doi: 10.1007/s00224-011-9312-0
  • Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. 2012. On exact algorithms for treewidth. ACM Transactions on Algorithms. 9. 23 pages. doi: 10.1145/2390176.2390188
  • Dorn, Frederic; Fomin, Fedor; Thilikos, Dimitrios M. 2012. Catalan structures and dynamic programming in H-minor-free graphs. Journal of computer and system sciences (Print). 78: 1606-1622. doi: 10.1016/j.jcss.2012.02.004
  • Fellows, Michael R.; Fomin, Fedor; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Villanger, Yngve. 2012. Local search: Is brute-force avoidable? Journal of computer and system sciences (Print). 78: 707-719. doi: 10.1016/j.jcss.2011.10.003
  • Fomin, Fedor. 2012. Kernelization algorithms (keynote speech). Smart Innovation, Systems and Technologies. 20: 1-7.
  • Fomin, Fedor; Fraigniaud, Pierre; Kreutzer, Stephan; Thilikos, Dimitrios. 2012. Foreword: Special Issue on Theory and Applications of Graph Searching Problems. Theoretical Computer Science. 463: 1-1. doi: 10.1016/j.tcs.2012.10.006
  • Fomin, Fedor; Gaspers, Serge; Golovach, Petr; Suchan, Karol; Szeider, Stefan; van Leeuwen, Erik Jan; Vatshelle, Martin; Villanger, Yngve. 2012. k-Gap Interval Graphs. Lecture Notes in Computer Science. 7256: 350-361.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel. 2012. Cops and robber game without recharging. Theory of Computing Systems. 50: 611-620. doi: 10.1007/s00224-011-9360-5
  • Fomin, Fedor; Golovach, Petr; Nederlof, Jesper; Pilipczuk, Michal Pawel. 2012. Minimizing Rosenthal potential in multicast games. Lecture Notes in Computer Science.
  • Fomin, Fedor; Golovach, Petr; Pralat, Pawel. 2012. Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 26: 571-590. doi: 10.1137/110837759
  • Fomin, Fedor; Grandoni, Fabrizio; Lokshtanov, Daniel; Saurabh, Saket. 2012. Sharp separation and applications to exact and parameterized algorithms. Algorithmica. 63: 692-706. doi: 10.1007/s00453-011-9555-9
  • Fomin, Fedor; Heggernes, Pinar; van Leeuwen, Erik Jan. 2012. Making Life Easier for Firefighters. Lecture Notes in Computer Science. 7288: 177-188. doi: 10.1007/978-3-642-30347-0_19
  • Fomin, Fedor; Jansen, Bart M.P.; Pilipczuk, Michal Pawel. 2012. Preprocessing subgraph and minor problems: when does a small vertex cover help? Lecture Notes in Computer Science.
  • Fomin, Fedor; Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket. 2012. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms (extended abstract). Proceedings ... annual Symposium on Foundations of Computer Science. 470-479. doi: 10.1109/FOCS.2012.62
  • Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket; Rao, B.V. Raghavendra. 2012. Faster algorithms for finding and counting subgraphs. Journal of computer and system sciences (Print). 78: 698-706. doi: 10.1016/j.jcss.2011.10.001
  • Fomin, Fedor; Saurabh, Saket; Villanger, Yngve. 2012. A Polynomial Kernel for Proper Interval Vertex Deletion. Lecture Notes in Computer Science. 7501: 467-478.
  • Fomin, Fedor; Villanger, Yngve. 2012. Subexponential parameterized algorithm for minimum fill-in. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1737-1746.
  • Fomin, Fedor; Villanger, Yngve. 2012. Treewidth computation and extremal combinatorics. Combinatorica. 32: 289-308. doi: 10.1007/s00493-012-2536-z
  • Adler, Isolde Marianne; Dorn, Frederic; Fomin, Fedor; Sau, Ignasi; Thilikos, Dimitrios M. 2011. Faster parameterized algorithms for minor containment. Theoretical Computer Science. 412: 7018-7028. doi: 10.1016/j.tcs.2011.09.015
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2011. Implicit branching and parameterized partial cover problems. Journal of computer and system sciences (Print). 77: 1159-1171. doi: 10.1016/j.jcss.2010.12.002
  • Bessy, Stephane; Fomin, Fedor; Gaspers, Serge; Paul, Christophe; Perez, Anthony; Saurabh, Saket; Thomasse, Stephane. 2011. Kernels for feedback arc set in tournaments. Journal of computer and system sciences (Print). 77: 1071-1078. doi: 10.1016/j.jcss.2010.10.001
  • Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr. 2011. Approximation of minimum weight spanners for sparse graphs. Theoretical Computer Science. 412: 846-852. doi: 10.1016/j.tcs.2010.11.034
  • Dragan, Feodor F.; Fomin, Fedor; Golovach, Petr. 2011. Spanners in sparse graphs. Journal of computer and system sciences (Print). 77: 1108-1119. doi: 10.1016/j.jcss.2010.10.002
  • Fellows, Michael R.; Fomin, Fedor; Gutin, Gregory. 2011. Special Issue on Parameterized Complexity of Discrete Optimization Preface. Discrete Optimization. 8: 1-1. doi: 10.1016/j.disopt.2011.02.001
  • Fellows, Michael R.; Fomin, Fedor; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Szeider, Stefan; Thomassen, Carsten. 2011. On the complexity of some colorful problems parameterized by treewidth. Information and Computation. 209: 143-153. doi: 10.1016/j.ic.2010.11.026
  • Fomin, Fedor; Geevarghese, Philip; Villanger, Yngve. 2011. Minimum Fill-in of Sparse Graphs: Kernelization and Approximation. Leibniz International Proceedings in Informatics. 13: 164-175. doi: 10.4230/LIPIcs.FSTTCS.2011.164
  • Fomin, Fedor; Golovach, Petr A.; Thilikos, Dimitrios M. 2011. Approximation Algorithms for Domination Search. Lecture Notes in Computer Science. 6534: 130-141. doi: 10.1007/978-3-642-18318-8_12
  • Fomin, Fedor; Golovach, Petr; Hall, Alex; Mihalák, Matúš; Vicari, Elias; Widmayer, Peter. 2011. How to Guard a Graph? Algorithmica. 61: 839-856. doi: 10.1007/s00453-009-9382-4
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2011. Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica. 61: 252-273. doi: 10.1007/s00453-010-9418-9
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel. 2011. Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 412: 6484-6497. doi: 10.1016/j.tcs.2011.08.024
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2011. Approximating width parameters of hypergraphs with excluded minors. SIAM Journal on Discrete Mathematics. 25: 1331-1348. doi: 10.1137/080743226
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. 2011. Contraction obstructions for treewidth. Journal of combinatorial theory. Series B (Print). 101: 302-314. doi: 10.1016/j.jctb.2011.02.008
  • Fomin, Fedor; Golovach, Petr; van Leeuwen, Erik Jan. 2011. Spanners of bounded degree graphs. Information Processing Letters. 111: 142-144. doi: 10.1016/j.ipl.2010.10.021
  • Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve. 2011. Enumerating minimal subset feedback vertex sets. Lecture Notes in Computer Science. 6844: 399-410. doi: 10.1007/978-3-642-22300-6_34
  • Fomin, Fedor; Kratochvil, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne. 2011. On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 68: 113-124. doi: 10.1002/jgt.20544
  • Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2011. Subexponential algorithms for partial cover problems. Information Processing Letters. 111: 814-818. doi: 10.1016/j.ipl.2011.05.016
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket. 2011. An exact algorithm for minimum distortion embedding. Theoretical Computer Science. 412: 3530-3536. doi: 10.1016/j.tcs.2011.02.043
  • Fomin, Fedor; Saurabh, Saket; Thilikos, Dimitrios M. 2011. Strengthening Erdos-Posa Property for Minor-Closed Graph Classes. Journal of Graph Theory. 66: 235-240. doi: 10.1002/jgt.20503
  • Fomin, Fedor; Todinca, Ioan; Villanger, Yngve. 2011. Exact Algorithm for the Maximum Induced Planar Subgraph Problem. Lecture Notes in Computer Science. 6942: 287-298. doi: 10.1007/978-3-642-23719-5_25
  • Adler, Isolde Marianne; Dorn, Frederic; Fomin, Fedor; Sau, Ignasi; Thilikos, Dimitrios. 2010. Faster Parameterized Algorithms for Minor Containment. Lecture Notes in Computer Science. 6139: 322-333.
  • Adler, Isolde Marianne; Dorn, Frederic; Fomin, Fedor; Sau, Ignasi; Thilikos, Dimitrios. 2010. Fast Minor Testing in Planar Graphs. Lecture Notes in Computer Science. 6346: 97-109.
  • Broersma, Hajo; Fomin, Fedor; van 't Hof, Pim; Paulusma, Daniel. 2010. Fast exact algorithms for Hamiltonicity in claw-free graphs. Lecture Notes in Computer Science. 5911: 44-53. doi: 10.1007/978-3-642-11409-0_4
  • Cohen, Nathann; Fomin, Fedor; Gutin, Gregory; Kim, Eun Jung; Saurabh, Saket; Yeo, Anders. 2010. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. Journal of computer and system sciences (Print). 76: 650-662. doi: 10.1016/j.jcss.2010.01.001
  • Dorn, Frederic; Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2010. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Leibniz International Proceedings in Informatics. 5: 251-262.
  • Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L.; Fomin, Fedor. 2010. Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica. 58: 790-810. doi: 10.1007/s00453-009-9296-1
  • Fomin, Fedor. 2010. Kernelization. Lecture Notes in Computer Science. 6072: 107-108. doi: 10.1007/978-3-642-13182-0_10
  • Fomin, Fedor. 2010. Protrusions in Graphs and Their Applications. Lecture Notes in Computer Science. 6478: 3-3. doi: 10.1007/978-3-642-17493-3_2
  • Fomin, Fedor; Gaspers, S; Golovach, PA; Kratsch, D; Saurabh, S. 2010. Parameterized algorithm for eternal vertex cover. Information Processing Letters. 110: 702-706. doi: 10.1016/j.ipl.2010.05.029
  • Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket. 2010. Iterative compression and exact algorithms. Theoretical Computer Science. 411: 1045-1053. doi: 10.1016/j.tcs.2009.11.012
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Nisse, Nicolas; Suchan, Karol. 2010. Pursuing a fast robber on a graph. Theoretical Computer Science. 411: 1167-1181. doi: 10.1016/j.tcs.2009.12.010
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 39: 1941-1956. doi: 10.1137/080742270
  • Fomin, Fedor; Heggernes, Pinar; Mihai, Rodica. 2010. Mixed Search Number and Linear-Width of Interval and Split Graphs. Networks. 56: 207-214. doi: 10.1002/net.20373
  • Fomin, Fedor; Oum, SI; Thilikos, DM. 2010. Rank-width and tree-width of H-minor-free graphs. European journal of combinatorics (Print). 31: 1617-1628. doi: 10.1016/j.ejc.2010.05.003
  • Fomin, Fedor; Villanger, Yngve. 2010. Finding Induced Subgraphs via Minimal Triangulations. Leibniz International Proceedings in Informatics. 5: 383-394.
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2009. Counting Subgraphs via Homomorphisms. Lecture Notes in Computer Science. 5555: 71-82. doi: 10.1007/978-3-642-02927-1_8
  • Bessy, Stephane; Fomin, Fedor; Gaspers, Serge; Paul, Christophe; Perez, Anthony; Saurabh, Saket; Thomasse, Stephane. 2009. Kernels for Feedback Arc Set In Tournaments. Leibniz International Proceedings in Informatics. 4: 37-47.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Paulusma, Daniel. 2009. Three Complexity Results on Coloring Pk-Free Graphs. Lecture Notes in Computer Science. 5874: 95-104. doi: 10.1007/978-3-642-10217-2_12
  • Cohen, Nathann; Fomin, Fedor; Gutin, Gregory; Kim, Eun Jung; Saurabh, Saket; Yeo, Anders. 2009. Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem. Lecture Notes in Computer Science. 5609: 37-46. doi: 10.1007/978-3-642-02882-3_5
  • Fellows, Michael; Fomin, Fedor; Lokshtanov, Daniel; Losievskaja, Elena; Rosamond, Frances; Saurabh, Saket. 2009. Distortion Is Fixed Parameter Tractable. Lecture Notes in Computer Science. 5555: 463-474. doi: 10.1007/978-3-642-02927-1_39
  • Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve. 2009. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Leibniz International Proceedings in Informatics. 3: 421-432.
  • Fomin, Fedor; Fraigniaud, Pierre; Nisse, Nicolas. 2009. Nondeterministic Graph Searching: From Pathwidth to Treewidth. Algorithmica. 53: 358-373. doi: 10.1007/s00453-007-9041-6
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket; Stepanov, Alexey. 2009. On two techniques of combining branching and treewidth. Algorithmica. 54: 181-207. doi: 10.1007/s00453-007-9133-3
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket; Thomasse, Stephane. 2009. A Linear Vertex Kernel for Maximum Internal Spanning Tree. Lecture Notes in Computer Science. 5878: 275-282. doi: http://dx.doi.org/10.1007/978-3-642-10631-6_29
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2009. Sort and Search: Exact algorithms for generalized domination. Information Processing Letters. 109: 795-798. doi: 10.1016/j.ipl.2009.03.023
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios. 2009. Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 3: 445-456. doi: 10.4230/LIPIcs.STACS.2009.1803
  • Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios. 2009. Contraction Bidimensionality: The Accurate Picture. Lecture Notes in Computer Science. 5757: 706-717. doi: http://dx.doi.org/10.1007/978-3-642-04128-0
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2009. A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM. 56. 32 pages. doi: 10.1145/1552285.1552286
  • Fomin, Fedor; Heggernes, Pinar; Mihai, Rodica. 2009. Mixed search number and linear-width of interval and split graphs. Networks. doi: 10.1002/net.20373
  • Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2009. Subexponential Algorithms for Partial Cover Problems. Leibniz International Proceedings in Informatics. 4: 193-201.
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket. 2009. An Exact Algorithm for Minimum Distortion Embedding. Lecture Notes in Computer Science. 5911: 112-121. doi: 10.1007/978-3-642-11409-0_10
  • Fomin, Fedor; Mazoit, Frederic; Todinca, Ioan. 2009. Computing branchwidth via efficient triangulations and blocks. Discrete Applied Mathematics. 157: 2726-2736. doi: 10.1016/j.dam.2008.08.009
  • Alon, Noga; Fomin, Fedor; Gutin, Gregory; Krivelevich, Michael; Saurabh, Saket. 2008. Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics. 23: 466-476. doi: 10.1137/070710494
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2008. Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract). Dagstuhl Seminar Proceedings. 08004. 12 pages.
  • Chen, Jianer; Fomin, Fedor; Liu, Yang; Lu, Songjian; Villanger, Yngve. 2008. Improved algorithms for feedback vertex set problems. Journal of computer and system sciences (Print). 74: 1188-1198. doi: 10.1016/j.jcss.2008.05.002
  • Dorn, Frederic Bernard; Fomin, Fedor; Thilikos, Dimitrios. 2008. Subexponential parameterized algorithms. Computer Science Review. 2: 29-39. doi: 10.1016/j.cosrev.2008.02.004
  • Dragan, Feodor; Fomin, Fedor; Golovach, Petr. 2008. A PTAS for the sparsest spanners problem on apex-minor-free graphs. Lecture Notes in Computer Science. 5162: 290-298.
  • Dragan, Feodor; Fomin, Fedor; Golovach, Petr. 2008. Spanners in sparse graphs. Lecture Notes in Computer Science. 5125: 597-608.
  • Fomin, Fedor; Fraigniaud, Pierre; Thilikos, Dimitrios M. 2008. Forewords: Special issue on graph searching. Theoretical Computer Science. 399: 157-157. doi: 10.1016/j.tcs.2008.02.034
  • Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket. 2008. Iterative Compression and Exact Algorithms. Lecture Notes in Computer Science. 5162: 335-346.
  • Fomin, Fedor; Gaspers, Serge; Pyatkin, Artem V; Razgon, Igor. 2008. On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica. 52: 293-307. doi: 10.1007/s00453-007-9152-0
  • Fomin, Fedor; Golovach, Petr; Hall, Alex; Mihalak, Matus; Vicari, Elias; Widmayer, Peter. 2008. How to guard a graph? Lecture Notes in Computer Science. 5369: 318-239.
  • Fomin, Fedor; Golovach, Petr; Kratochvil, Jan. 2008. On tractability cops and robbers game. IFIP International Federation for Information Processing. 237: 171-185.
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2008. Solving connected dominating set faster than 2(n). Algorithmica. 52: 153-166. doi: 10.1007/s00453-007-9145-z
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2008. Faster Steiner Tree Computation in Polynomial-Space. Lecture Notes in Computer Science. 5193: 430-441.
  • Fomin, Fedor; Grandoni, Fabrizio; Pyatkin, Artem V; Stepanov, Alexey. 2008. Combinatorial Bounds via Measure and Conquer: Bounding Minimal Dominating Sets and Applications. ACM Transactions on Algorithms. 5. 17 pages. doi: 10.1145/1435375.1435384
  • Fomin, Fedor; Iwama, Kazuo; Kratsch, Dieter. 2008. Abstracts Collection -- Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings. 08431.
  • Fomin, Fedor; Iwama, Kazuo; Kratsch, Dieter. 2008. 08431 Executive Summary -- Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings. 08431. 3 pages.
  • Fomin, Fedor; Kratochvil, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne. 2008. On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science. 4957: 194-205.
  • Fomin, Fedor; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve. 2008. Exact algorithms for treewidth and minimum fill-in. SIAM journal on computing (Print). 38: 1058-1079. doi: 10.1137/050643350
  • Fomin, Fedor; Thilikos, Dimitrios M. 2008. An annotated bibliography on guaranteed graph searching. Theoretical Computer Science. 399: 236-245. doi: 10.1016/j.tcs.2008.02.040
  • Fomin, Fedor; Villanger, Yngve. 2008. Treewidth Computation and Extremal Combinatorics. Lecture Notes in Computer Science. 5125: 210-221.
  • Alon, Noga; Fomin, Fedor; Gutin, Gregory; Krivelevich, Michael; Saurabh, Saket. 2007. Better Algorithms and Bounds for Directed Maximum Leaf Problems. Lecture Notes in Computer Science. 4855: 316-327.
  • Alon, Noga; Fomin, Fedor; Gutin, Gregory; Krivelevich, Michael; Saurabh, Saket. 2007. Parameterized Algorithms for Directed Maximum Leaf Problems. Lecture Notes in Computer Science. 4596: 352-362.
  • Broersma, Hajo; Fomin, Fedor; Golovach, Petr; Woeginger, Gerhard J. 2007. Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory. 55: 137-152. doi: 10.1002/jgt.20228
  • Broersma, Hajo; Fomin, Fedor; Kralovic, Rastislav; Woeginger, Gerhard J. 2007. Eliminating graphs by means of parallel knock-out schemes. Discrete Applied Mathematics. 155: 92-102. doi: 10.1016/j.dam.2006.04.034
  • Chen, Jianer; Fomin, Fedor; Liu, Yang; Lu, Songjian; Villanger, Yngve. 2007. Improved Algorithms for the Feedback Vertex Set Problems. Lecture Notes in Computer Science. 4619: 422-433.
  • Dorn, Frederic Bernard; Fomin, Fedor; Thilikos, Dimitrios. 2007. Subexponential Parameterized Algorithms. Lecture Notes in Computer Science. 4596: 15-27.
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket. 2007. Improved Exact Algorithms for Counting 3- and 4-Colorings. Lecture Notes in Computer Science. 4598: 65-74.
  • Fomin, Fedor; Heggernes, Pinar; Kratschz, Dieter. 2007. Exact algorithms for graph homomorphisms. Theory of Computing Systems. 41: 381-393. doi: 10.1007/s00224-007-2007-x
  • Fomin, Fedor; Heggernes, Pinar; Mihai, Rodica Georgeta. 2007. Mixed search number and linear-width of interval and split graphs. Lecture Notes in Computer Science. 4769: 304-315.
  • Fomin, Fedor; Thilikos, Dimitrios M. 2007. On self duality of pathwidth in polyhedral graph embeddings. Journal of Graph Theory. 55: 42-54. doi: 10.1002/jgt.20219
  • Golovach, Petr; Fomin, Fedor; Kratochvil, Jan; Kratsch, Dieter; Liedloff, Mathieu. 2007. Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science. 4619: 507-518.
  • Bodlaender, Hans; Fomin, Fedor; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios. 2006. On exact algorithms for treewidth. Lecture Notes in Computer Science. 4168: 672-683.
  • Broersma, Hajo; Fomin, Fedor; Kratochvil, Jan; Woeginger, Gerhard J. 2006. Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult. Algorithmica. 44: 343-361. doi: 10.1007/s00453-005-1176-8
  • Cohen, Johanne; Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Kucherov, Gregory. 2006. Optimal linear arrangement of interval graphs. Lecture Notes in Computer Science. 4162,: 267-279. doi: 10.1007/11821069_24
  • Dorn, Frederic Bernard; Fomin, Fedor; Thilikos, Dimitrios M. 2006. Fast subexponential algorithm for non-local problems on graphs of bounded genus. Lecture Notes in Computer Science. 4059: 172-183. doi: 10.1007/11785293_18
  • Fomin, Fedor; Gaspers, Serge; Pyatkin, Artem V. 2006. Finding a Minimum Feedback Vertex Set in time O(1.7548n). Lecture Notes in Computer Science. 4169: 184-191.
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket. 2006. Branching and treewidth based exact algorithms. Lecture Notes in Computer Science. 4288: 16-25.
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2006. Solving Connected Dominating Set Faster than O(2n). Lecture Notes in Computer Science. 4337: 152-163.
  • Fomin, Fedor; Høie, Kjartan. 2006. Pathwidth of cubic graphs and exact algorithms. Information Processing Letters. 97: 191-196. doi: 10.1016/j.ipl.2005.10.012
  • Fomin, Fedor; Thilikos, Dimitrios. 2006. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM journal on computing (Print). 36: 281-309. doi: 10.1137/S0097539702419649
  • Fomin, Fedor; Thilikos, Dimitrios. 2006. A 3-approximation for the pathwidth of Halin graphs. Journal of Discrete Algorithms. 4: 499-510.
  • Fomin, Fedor; Thilikos, Dimitrios M. 2006. New upper bounds on the decomposability of planar graphs. Journal of Graph Theory. 51: 53-81. doi: 10.1002/jgt.20121
  • Bodlaender, Hans; Fomin, Fedor. 2005. Tree decompositions with small cost. Discrete Applied Mathematics. 145: 143-154.
  • Bodlaender, Hans; Fomin, Fedor. 2005. Equitable colorings of bounded treewidth graphs. Theoretical Computer Science. 340: 22-30. doi: 10.1016/j.tcs.2005.09.027
  • Demaine, Eric; Fomin, Fedor; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios. 2005. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. Journal of the ACM. 52: 866-893.
  • Demaine, Erik D.; Fomin, Fedor; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios. 2005. Bidimensional parameters and local treewidth. SIAM Journal on Discrete Mathematics. 18: 501-511.
  • Demaine, Erik D.; Fomin, Fedor; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. 2005. Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Transactions on Algorithms. 1: 33-47. doi: http://doi.acm.org/10.1145/107
  • Dorn, Frederic Bernard; Penninkx, Elko; Bodlaender, Hans; Fomin, Fedor. 2005. Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. Lecture Notes in Computer Science. 3669: 95-106.
  • Fomin, Fedor; Fraigniaud, Pierre; Nisse, Nicolas. 2005. Nondeterministic Graph Searching: From Pathwidth to Treewidth. Lecture Notes in Computer Science. 3618: 364-375.
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2005. Measure and conquer: Domination - A case study. Lecture Notes in Computer Science. 3580: 191-203.
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2005. Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the European Association for Theoretical Computer Science. 87: 47-77.
  • Fomin, Fedor; Grandoni, Fabrizio; Pyatkin, Artem V; Stepanov, Alexey. 2005. Bounding the number of minimal dominating sets: A measure and conquer approach. Lecture Notes in Computer Science. 3827: 573-582.
  • Fomin, Fedor; Grandoni, Fabrizio; Pyatkin, Artem V; Stepanov, Alexey. 2005. On maximum number of minimal dominating sets in graphs. Electronic Notes in Discrete Mathematics. 22: 157-162. doi: doi:10.1016/j.endm.2005.06.028
  • Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter. 2005. Exact algorithms for graph homomorphisms. Lecture Notes in Computer Science. 3623: 161-171.
  • Fomin, Fedor; Mazoit, Frederic; Todinca, Ioan. 2005. Computing branchwidth via efficient triangulations and blocks. Lecture Notes in Computer Science. 3787: 374-384.
  • Fomin, Fedor; Thilikos, Dimitrios; Todinca, Ioan. 2005. Connected Graph Searching in Outerplanar Graphs. Electronic Notes in Discrete Mathematics. 22: 157-162. doi: doi:10.1016/j.endm.2005.06.028
  • Bodlaender, Hans L.; Broersma, Hajo; Fomin, Fedor; Pyatkin, Artem V; Woeginger, Gerhard J. 2004. Radio labeling with preassigned frequencies. SIAM Journal on Optimization. 15: 1-16.
  • Bodlaender, Hans; Fomin, Fedor. 2004. Equitable colorings of bounded treewidth graphs. Lecture Notes in Computer Science. 3153: 180-190.
  • Broersma, Hajo; Fomin, Fedor; Golovach, PA; Woeginger, GJ. 2004. Backbone colorings for networks. Lecture Notes in Computer Science. 2880: 131-142.
  • Broersma, Hajo; Fomin, Fedor; Woeginger, Gerhard J. 2004. Parallel knock-out schemes in networks,. Lecture Notes in Computer Science. 3153: 204-214.
  • Demaine, Eric; Fomin, Fedor; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios. 2004. Bidimensional parameters and local treewidth. Lecture Notes in Computer Science. 2976: 109-118.
  • Demaine, Eric; Fomin, Fedor; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios. 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.
  • Fiala, Jiri; Fishkin, Alexey; Fomin, Fedor. 2004. On distance constrained labeling of disk graphs. Theoretical Computer Science. 326: 261-292.
  • Fomin, Fedor. 2004. Searching expenditure and interval graphs. Discrete Applied Mathematics. 135: 97-104.
  • Fomin, Fedor; Fiala, Jiri; Fishkin, Alexei. 2004. On distance constrained labeling of disk graphs. Theoretical Computer Science. 326: 261-292.
  • Fomin, Fedor; Heggernes, Pinar; Telle, Jan Arne. 2004. Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica. 41: 73-87. doi: 10.1007/s00453-004-1117-y
  • Fomin, Fedor; Kratsch, Dieter; Müller, Haiko. 2004. Algorithms for graphs with small octopus. Discrete Applied Mathematics. 134: 105-128.
  • Fomin, Fedor; Kratsch, Dieter; Todinca, Ioan. 2004. Exact (exponential) algorithms for treewidth and minimum fill-in. Lecture Notes in Computer Science. 3142: 568-580.
  • Fomin, Fedor; Kratsch, Dieter; Woeginger, Gerhard. 2004. Exact (exponential) algorithms for the dominating set problem. Lecture Notes in Computer Science. 3353: 245-256.
  • Fomin, Fedor; Matamala, Martin; Prisner, Erich; Rapaport, Ivan. 2004. AT-free graphs: linear bounds for the oriented diameter. Discrete Applied Mathematics. 141: 135-148.
  • Fomin, Fedor; Matamala, Martin; Rapaport, Ivan. 2004. The complexity of approximating the oriented diameter of chordal graphs. Journal of Graph Theory. 45: 255-269.
  • Fomin, Fedor; Thilikos, Dimitrios. 2004. Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. Lecture Notes in Computer Science. 3142: 581-592.
  • Fomin, Fedor; Thilikos, Dimitrios. 2004. A simple and fast approach for solving problems on planar graphs. Lecture Notes in Computer Science. 2996: 56-67.
  • Fomin, Fedor; Thilikos, Dimitrios. 2004. Dominating sets and local treewidth. Lecture Notes in Computer Science. 2832: 221-229.
  • Fomin, Fedor. 2003. Pathwidth of planar and line graphs. Graphs and Combinatorics. 19: 91-99.
  • Golovach, Petr; Fomin, Fedor. 2003. Interval degree and bandwidth of a graph. Discrete Applied Mathematics. 129: 345-359.
  • Kratsch, Dieter; Müller, Haiko, Haiko; Fomin, Fedor. 2003. On the domination search numbe. Discrete Applied Mathematics. 127: 565-580.
  • Thilikos, Dimitrios; Fomin, Fedor. 2003. On the Monotonicity of Games Generated by Symmetric Submodular Functions. Discrete Applied Mathematics. 131: 323-335.
  • Fomin, Fedor. 2002. A generalization of the graph bandwidth. Vestnik St. Petersburg Univ. Math.. 34 (2001): 15-19.
  • Fomin, Fedor; Bodlaender, Hans. 2002. Approximation of pathwidth of outerplanar graphs. Journal of Algorithms. 42: 190-200.
  • Fomin, Fedor; Broersma, Hajo; Woeginger, Gerhard; Nesetril, Jaroslav. 2002. More About Subcolorings. Computing. 69: 187-203.
Book sections
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2013. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. Extended abstract, pages 79-90. In:
    • Seth, Anil; Vishnoi, Nisheeth. 2013. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India. 539 pages. ISBN: 978-3-939897-64-4.
  • Chitnis, Rajesh; Fomin, Fedor; Golovach, Petr. 2013. Preventing unraveling in social networks gets harder. Extended abstract. In:
    • desJardins, Marie; Littman, Michael. 2013. Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press. ISBN: 978-1-57735-615-8.
  • Fellows, Michael; Rosamond, Frances; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve. 2009. Local Search: Is Brute-Force Avoidable? Raport, pages 486-491. In:
    • Boutilier, Craig. 2009. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press. 2106 pages. ISBN: 978-1-57735-426-0.
  • Dorn, Frederic; Fomin, Fedor; Thilikos, Dimitrios M. 2008. Catalan structures and dynamic programming in /H/-minor-free graphs. -, pages 631-640. In:
    • Teng, Shang-Hua. 2008. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008. Society for Industrial and Applied Mathematics. 1279 pages. ISBN: 0-89871-585-7.
  • Fomin, Fedor; Thilikos, Dimitrios. 2008. Branchwidth of Graphs. 2, pages 1-99. In:
    • Kao, Ming-Yang. 2008. Encyclopedia of Algorithms. Springer. 1166 pages. ISBN: 978-0-387-30770-1.
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter. 2006. Measure and conquer: a simple O(2 0.288n) independent set algorithm. Kapittel, pages 18-25. In:
    • Stein, Cliff. 2006. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. ACM Press. 1261 pages. ISBN: 0-89871-605-5.

More information in national current research information system (CRIStin)