Publications

From preprocessing
Jump to: navigation, search

Book

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\'aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh - Parameterized Algorithms
Springer,2015
http://dx.doi.org/10.1007/978-3-319-21275-3
Bibtex
Author : Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\'aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Title : Parameterized Algorithms
In : -
Address :
Date : 2015

Conferences

2016

Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Saket Saurabh - Editing to Connected f-Degree Graph
33rd Symposium on Theoretical Aspects of Computer Science, {STACS} 2016, February 17-20, 2016, Orl{\'{e}}ans, France pp. 36:1--36:14,2016
http://dx.doi.org/10.4230/LIPIcs.STACS.2016.36
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Saket Saurabh
Title : Editing to Connected f-Degree Graph
In : 33rd Symposium on Theoretical Aspects of Computer Science, {STACS} 2016, February 17-20, 2016, Orl{\'{e}}ans, France -
Address :
Date : 2016

P\aal Gr\on\aas Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sanchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar - Kernelization and Sparseness: the Case of Dominating Set
33rd Symposium on Theoretical Aspects of Computer Science, {STACS} 2016, February 17-20, 2016, Orl{\'{e}}ans, France pp. 31:1--31:14,2016
http://dx.doi.org/10.4230/LIPIcs.STACS.2016.31
Bibtex
Author : P\aal Gr\on\aas Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sanchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar
Title : Kernelization and Sparseness: the Case of Dominating Set
In : 33rd Symposium on Theoretical Aspects of Computer Science, {STACS} 2016, February 17-20, 2016, Orl{\'{e}}ans, France -
Address :
Date : 2016

Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala - Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016 pp. 1643--1649,2016
http://dx.doi.org/10.1137/1.9781611974331.ch112
Bibtex
Author : Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Title : Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
In : Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016 -
Address :
Date : 2016

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk - Subexponential parameterized algorithm for Interval Completion
Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016 pp. 1116--1131,2016
http://dx.doi.org/10.1137/1.9781611974331.ch78
Bibtex
Author : Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk
Title : Subexponential parameterized algorithm for Interval Completion
In : Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016 -
Address :
Date : 2016

2015

Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh - Parameterized Complexity of Superstring Problems
Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings 9133:89-99,2015
http://dx.doi.org/10.1007/978-3-319-19929-0_8
Bibtex
Author : Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
Title : Parameterized Complexity of Superstring Problems
In : Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings -
Address :
Date : 2015

Konrad Kazimierz Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma, Dimitrios M. Thilikos - Editing to a Planar Graph of Given Degrees
Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings 9139:143--156,2015
http://dx.doi.org/10.1007/978-3-319-20297-6_10
Bibtex
Author : Konrad Kazimierz Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma, Dimitrios M. Thilikos
Title : Editing to a Planar Graph of Given Degrees
In : Computer Science - Theory and Applications - 10th International Computer
              Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July
13-17, 2015, Proceedings -
Address :
Date : 2015

Pål Grønås Drange, Markus Dregi, Daniel Lokshtanov, Blair D. Sullivan - On the threshold of intractability
European Symposium on Algorithms (ESA) ,2015
http://arxiv.org/abs/1505.00612
Bibtex
Author : Pål Grønås Drange, Markus Dregi, Daniel Lokshtanov, Blair D. Sullivan
Title : On the threshold of intractability
In : European Symposium on Algorithms (ESA) -
Address :
Date : 2015

Pål Grønås Drange, Michał Pilipczuk - A Polynomial Kernel for Trivially Perfect Editing
European Symposium on Algorithms (ESA) ,2015
http://arxiv.org/abs/1412.7558
Bibtex
Author : Pål Grønås Drange, Michał Pilipczuk
Title : A Polynomial Kernel for Trivially Perfect Editing
In : European Symposium on Algorithms (ESA) -
Address :
Date : 2015

2014

Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma - Editing to Eulerian Graphs
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) 29:97--108, Dagstuhl, Germany,2014
http://drops.dagstuhl.de/opus/volltexte/2014/4835
Bibtex
Author : Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma
Title : Editing to Eulerian Graphs
In : 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) -
Address : Dagstuhl, Germany
Date : 2014

Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Saket Saurabh - Connecting Vertices by Independent Trees
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) 29:73--84, Dagstuhl, Germany,2014
http://drops.dagstuhl.de/opus/volltexte/2014/4834
Bibtex
Author : Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Saket Saurabh
Title : Connecting Vertices by Independent Trees
In : 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) -
Address : Dagstuhl, Germany
Date : 2014

Petr A. Golovach, Marcin Jakub Kaminski, Spyridon Maniatis, Dimitrios M. Thilikos - The Parameterized Complexity of Graph Cyclability
ESA 2014, LNCS 8737:492--504,2014
http://dx.doi.org/10.1007/978-3-662-44777-2_41
Bibtex
Author : Petr A. Golovach, Marcin Jakub Kaminski, Spyridon Maniatis, Dimitrios M. Thilikos
Title : The Parameterized Complexity of Graph Cyclability
In : ESA 2014, LNCS -
Address :
Date : 2014

Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Christophe Paul - Hadwiger Number of Graphs with Small Chordality
WG 2014, LNCS 8747:201--213,2014
http://dx.doi.org/10.1007/978-3-319-12340-0_17
Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Christophe Paul
Title : Hadwiger Number of Graphs with Small Chordality
In : WG 2014, LNCS -
Address :
Date : 2014

Petr A. Golovach, Daniel Paulusma, Erik Jan van Leeuwen - Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
WG 2014, LNCS 8747:225--237,2014
http://dx.doi.org/10.1007/978-3-319-12340-0_19
Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Erik Jan van Leeuwen
Title : Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
In : WG 2014, LNCS -
Address :
Date : 2014

Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof - On the Computational Complexity of Vertex Integrity and Component Order Connectivity
Algorithms and Computation - 25th International Symposium (ISAAC 2014), Jeonju, Korea, December 15-17, 2014, Proceedings 8889:285--297,2014
http://dx.doi.org/10.1007/978-3-319-13075-0_23
Bibtex
Author : Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof
Title : On the Computational Complexity of Vertex Integrity and Component Order Connectivity
In : Algorithms and Computation - 25th International Symposium (ISAAC 2014), Jeonju, Korea, December 15-17, 2014, Proceedings -
Address :
Date : 2014

Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh - Parameterized Algorithms to Preserve Connectivity
Proceedings of 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), track A, LNCS 8572:800-811,2014
http://dx.doi.org/10.1007/978-3-662-43948-7_66
Bibtex
Author : Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh
Title : Parameterized Algorithms to Preserve Connectivity
In : Proceedings of 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), track A, LNCS -
Address :
Date : 2014

Fedor V. Fomin, Daniel Lokshtanov,, Saket Saurabh - Efficient computation of representative sets with applications in parameterized and exact algorithms
Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 142– 151,2014
http://arxiv.org/abs/1304.4626
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov,, Saket Saurabh
Title : Efficient computation of representative sets with applications in parameterized and exact algorithms
In : Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA) -
Address :
Date : 2014

Fedor V. Fomin, Ioan Todinca,, Yngve Villanger - Large induced subgraphs via triangulations and {CMSO}
Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 582–583,2014
http://arxiv.org/abs/1309.1559
Bibtex
Author : Fedor V. Fomin, Ioan Todinca,, Yngve Villanger
Title : Large induced subgraphs via triangulations and {CMSO}
In : Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA) -
Address :
Date : 2014

Claire David, Piotr Hofman, Filip Murlak, Michał Pilipczuk - Synthesizing transformations from XML schema mappings
17th International Conference on Database Theory (ICDT 2014) ,2014
Bibtex
Author : Claire David, Piotr Hofman, Filip Murlak, Michał Pilipczuk
Title : Synthesizing transformations from XML schema mappings
In : 17th International Conference on Database Theory (ICDT 2014) -
Address :
Date : 2014

Pål Grønas Drange, Fedor V. Fomin, Michal Pilipczuk, Yngve Villanger - {Exploring Subexponential Parameterized Complexity of Completion Problems}
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) 25:288--299, Dagstuhl, Germany,2014
http://drops.dagstuhl.de/opus/volltexte/2014/4465
Bibtex
Author : Pål Grønas Drange, Fedor V. Fomin, Michal Pilipczuk, Yngve Villanger
Title : {Exploring Subexponential Parameterized Complexity of Completion Problems}
In : 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) -
Address : Dagstuhl, Germany
Date : 2014

D\'aniel Marx, Michal Pilipczuk - {Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)}
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) 25:542--553, Dagstuhl, Germany,2014
http://drops.dagstuhl.de/opus/volltexte/2014/4486
Bibtex
Author : D\'aniel Marx, Michal Pilipczuk
Title : {Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)}
In : 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) -
Address : Dagstuhl, Germany
Date : 2014

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh - Minimum bisection is fixed parameter tractable
Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA, May 31 - June 03, 2014 pp. 323--332,2014
http://doi.acm.org/10.1145/2591796.2591852
Bibtex
Author : Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Title : Minimum bisection is fixed parameter tractable
In : Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA, May 31 - June 03, 2014 -
Address :
Date : 2014

Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh - Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2014, Philadelphia, PA, USA, October 18-21, 2014 pp. 186--195,2014
http://dx.doi.org/10.1109/FOCS.2014.28
Bibtex
Author : Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Title : Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs
              of Bounded Treewidth
In : 55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014 -
Address :
Date : 2014

2013

Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh - Partially Polynomial Kernels for Set cover and Test Cover
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) 24:67--78, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/4362
Bibtex
Author : Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, Saket Saurabh
Title : Partially Polynomial Kernels for Set cover and Test Cover
In : IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) -
Address : Dagstuhl, Germany
Date : 2013

Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach - Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) 24:79--90, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/4363
Bibtex
Author : Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach
Title : Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
In : IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) -
Address : Dagstuhl, Germany
Date : 2013

Remy Belmonte, Petr A. Golovach, Pim van't Hof, Daniel Paulusma - Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS 8246:16-27,2013
Pdf Bibtex
Author : Remy Belmonte, Petr A. Golovach, Pim van't Hof, Daniel Paulusma
Title : Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
In : Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS -
Address :
Date : 2013
Fedor V. Fomin, Daniel Lokshtanov, Rajesh Chitnis, Pranabendu Misra, Ramanujan M. S., and Saket Saurabh - Faster Exact Algorithms for Some Terminal Set Problems
Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS 8246:150-162,2013
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov, Rajesh Chitnis, Pranabendu Misra, Ramanujan M. S., and Saket Saurabh
Title : Faster Exact Algorithms for Some Terminal Set Problems
In : Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS -
Address :
Date : 2013
Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk - Computing tree-depth faster than 2^n
Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS 8246:137-149,2013
http://arxiv.org/abs/1306.3857
Bibtex
Author : Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk
Title : Computing tree-depth faster than 2^n
In : Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS -
Address :
Date : 2013
Hajo Broersma, Jean-Francois Couturier, Jiri Fiala, Petr A. Golovach, Tomas Kaiser, Daniel Paulusma, Andrzej Proskurowski - Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
Proceedings of 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), LNCS 8165:127-138,2013
http://arxiv.org/abs/1301.5953
Bibtex
Author : Hajo Broersma, Jean-Francois Couturier, Jiri Fiala, Petr A. Golovach, Tomas Kaiser, Daniel Paulusma, Andrzej Proskurowski
Title : Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
In : Proceedings of 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), LNCS -
Address :
Date : 2013
Konrad K. Dabrowski, Petr A. Golovach, Daniel Paulusma - Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
Proceedings of 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), LNCS 8165:201-212,2013
Pdf Bibtex
Author : Konrad K. Dabrowski, Petr A. Golovach, Daniel Paulusma
Title : Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
In : Proceedings of 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), LNCS -
Address :
Date : 2013
Manfred Cochefert, Jean-Francois Couturier, Petr A. Golovach, Dieter Kratsch, Daniel Paulusma - Sparse Square Roots
Proceedings of 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), LNCS 8165:177-188,2013
http://arxiv.org/abs/1310.5469
Bibtex
Author : Manfred Cochefert, Jean-Francois Couturier, Petr A. Golovach, Dieter Kratsch, Daniel Paulusma
Title : Sparse Square Roots
In : Proceedings of 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), LNCS -
Address :
Date : 2013
Petr A. Golovach, Daniel Paulusma, Iain Stewart - Graph Editing to a Fixed Target
Proceedings of International Workshop on Combinatorial Algorithms (IWOCA 2013), LNCS 8288:192-205,2013
Pdf Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Iain Stewart
Title : Graph Editing to a Fixed Target
In : Proceedings of International Workshop on Combinatorial Algorithms (IWOCA 2013), LNCS -
Address :
Date : 2013
Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen - On the Parameterized Complexity of Cutting a Few Vertices from a Graph
Proceedings of 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), LNCS 8087:421-432,2013
http://arxiv.org/abs/1304.6189
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen
Title : On the Parameterized Complexity of Cutting a Few Vertices from a Graph
In : Proceedings of 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), LNCS -
Address :
Date : 2013
Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach - Preventing Unraveling in Social Networks Gets Harder
Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013) ,2013
http://arxiv.org/abs/1304.5870
Bibtex
Author : Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach
Title : Preventing Unraveling in Social Networks Gets Harder
In : Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013) -
Address :
Date : 2013
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk - The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
Proceedings of 54th Annual Symposium on Foundations of Computer Science (FOCS 2013) pp. 197-207,2013
http://arxiv.org/abs/1304.4207
Bibtex
Author : Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
Title : The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
In : Proceedings of 54th Annual Symposium on Foundations of Computer Science (FOCS 2013) -
Address :
Date : 2013
Hans L. Bodlaender, Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk - An O(c^k n) 5-approximation algorithm for treewidth
Proceedings of 54th Annual Symposium on Foundations of Computer Science (FOCS 2013) pp. 499-508,2013
http://arxiv.org/abs/1304.6321
Bibtex
Author : Hans L. Bodlaender, Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk
Title : An O(c^k n) 5-approximation algorithm for treewidth
In : Proceedings of 54th Annual Symposium on Foundations of Computer Science (FOCS 2013) -
Address :
Date : 2013
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger - Largest chordal and interval subgraphs faster than 2^n
Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), LNCS 8125:193-204,2013
Bibtex
Author : Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger
Title : Largest chordal and interval subgraphs faster than 2^n
In : Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), LNCS -
Address :
Date : 2013
Fedor V. Fomin, Michał Pilipczuk - Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), LNCS 8125:505-516
http://arxiv.org/abs/1301.7314
Bibtex
Author : Fedor V. Fomin, Michał Pilipczuk
Title : Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
In : Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), LNCS -
Address :
Date :
Fedor V. Fomin, Petr A. Golovach - Long Circuits and Large Euler Subgraphs
Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), LNCS 8125:493-504
http://arxiv.org/abs/1304.5746
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach
Title : Long Circuits and Large Euler Subgraphs
In : Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), LNCS -
Address :
Date :
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Yngve Villanger - An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
Proceedings of 40th International Colloquium on Automata, Languages, and Programming, Part I (ICALP 2013), LNCS 7965:485-496,2013
Pdf Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Yngve Villanger
Title : An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
In : Proceedings of 40th International Colloquium on Automata, Languages, and Programming, Part I (ICALP 2013), LNCS -
Address :
Date : 2013
Petr A. Golovach, Daniel Paulusma - List Coloring in the Absence of Two Subgraphs
Proceedings of 8th International Conference on Algorithms and Complexity (CIAC 2013), LNCS 7878:288-299,2013
Pdf Bibtex
Author : Petr A. Golovach, Daniel Paulusma
Title : List Coloring in the Absence of Two Subgraphs
In : Proceedings of 8th International Conference on Algorithms and Complexity (CIAC 2013), LNCS -
Address :
Date : 2013
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey - Cliques and Clubs
Proceedings of 8th International Conference on Algorithms and Complexity (CIAC 2013), LNCS 7878:276-287,2013
Pdf Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey
Title : Cliques and Clubs
In : Proceedings of 8th International Conference on Algorithms and Complexity (CIAC 2013), LNCS -
Address :
Date : 2013
Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen - Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) 20:353--364, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/3947
Bibtex
Author : Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen
Title : Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
In : 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) -
Address : Dagstuhl, Germany
Date : 2013
Michal Pilipczuk - Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) 20:197--208, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/3934
Bibtex
Author : Michal Pilipczuk
Title : Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
In : 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) -
Address : Dagstuhl, Germany
Date : 2013
Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger - Tight bounds for Parameterized Complexity of Cluster Editing
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) 20:32--43, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/3920
Bibtex
Author : Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Yngve Villanger
Title : Tight bounds for Parameterized Complexity of Cluster Editing
In : 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) -
Address : Dagstuhl, Germany
Date : 2013
Fedor V. Fomin, Yngve Villanger - Searching for better fill-in
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) 20:8--19, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/3918
Bibtex
Author : Fedor V. Fomin, Yngve Villanger
Title : Searching for better fill-in
In : 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) -
Address : Dagstuhl, Germany
Date : 2013
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos - Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) 20:92--103, Dagstuhl, Germany,2013
http://drops.dagstuhl.de/opus/volltexte/2013/3925
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos
Title : Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
In : 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) -
Address : Dagstuhl, Germany
Date : 2013
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk - Known algorithms for Edge Clique Cover are probably optimal
Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 1044--1053,2012
http://arxiv.org/abs/1203.1754
Bibtex
Author : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk
Title : Known algorithms for Edge Clique Cover are probably optimal
In : Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA) -
Address :
Date : 2012
Fedor V. Fomin, Michał Pilipczuk - Jungles, bundles, and fixed parameter tractability
Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 396--413,2012
http://arxiv.org/abs/1112.1538
Bibtex
Author : Fedor V. Fomin, Michał Pilipczuk
Title : Jungles, bundles, and fixed parameter tractability
In : Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA) -
Address :
Date : 2012

2012

Petr A. Golovach, Dieter Kratsch, Daniel Paulusma - Detecting Induced Minors in AT-Free Graphs
Proceedings of the 23th International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676:495-505,2012
Pdf Bibtex
Author : Petr A. Golovach, Dieter Kratsch, Daniel Paulusma
Title : Detecting Induced Minors in AT-Free Graphs
In : Proceedings of the 23th International Symposium on Algorithms and Computation (ISAAC 2012), LNCS -
Address :
Date : 2012
Petr A. Golovach, Daniel Paulusma, Jian Song - Closing Complexity Gaps for Coloring Problems on H-Free Graphs
Proceedings of the 23th International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676:14-23,2012
Pdf Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Jian Song
Title : Closing Complexity Gaps for Coloring Problems on H-Free Graphs
In : Proceedings of the 23th International Symposium on Algorithms and Computation (ISAAC 2012), LNCS -
Address :
Date : 2012
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh - Planar {F}-Deletion: Approximation, Kernelization and Optimal {FPT} Algorithms
Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012) pp. 470-479,2012
http://arxiv.org/abs/1204.4230
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh
Title : Planar {F}-Deletion: Approximation, Kernelization and Optimal {FPT} Algorithms
In : Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012) -
Address :
Date : 2012
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk - Designing {FPT} algorithms for cut problems using randomized contractions
Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012) pp. 460-469,2012
http://arxiv.org/abs/1207.4079
Bibtex
Author : Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michał Pilipczuk
Title : Designing {FPT} algorithms for cut problems using randomized contractions
In : Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012) -
Address :
Date : 2012
Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk - Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
Proceedings of 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS 7535:97-108,2012
http://arxiv.org/abs/1206.4912
Bibtex
Author : Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk
Title : Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
In : Proceedings of 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS -
Address :
Date : 2012
Marcin Pilipczuk, Michał Pilipczuk - Finding a Maximum Induced Degenerate Subgraph Faster Than 2^n
Proceedings of 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS 7535:3-12,2012
http://arxiv.org/abs/1208.4449
Bibtex
Author : Marcin Pilipczuk, Michał Pilipczuk
Title : Finding a Maximum Induced Degenerate Subgraph Faster Than 2^n
In : Proceedings of 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS -
Address :
Date : 2012
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei - An exact algorithm for subset feedback vertex set on chordal graphs
Proceedings of 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS 7535:85-96,2012
Pdf Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
Title : An exact algorithm for subset feedback vertex set on chordal graphs
In : Proceedings of 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS -
Address :
Date : 2012
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk - On group feedback vertex set parameterized by the size of the cutset
Proceedings of 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012), LNCS 7551:194--205,2012
http://arxiv.org/abs/1112.6255
Bibtex
Author : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk
Title : On group feedback vertex set parameterized by the size of the cutset
In : Proceedings of 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012), LNCS -
Address :
Date : 2012
Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma, Michał Pilipczuk - How to eliminate a graph
Proceedings of 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012), LNCS 7551:320--331,2012
Pdf Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma, Michał Pilipczuk
Title : How to eliminate a graph
In : Proceedings of 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012), LNCS -
Address :
Date : 2012
Fedor V. Fomin, Saket Saurabh, Yngve Villanger - A Polynomial kernel for Proper Interval Vertex Deletion
Proceedings of 20th European Symposium on Algorithms (ESA 2012), LNCS 7501:467-478,2012
http://arxiv.org/abs/1204.4880
Bibtex
Author : Fedor V. Fomin, Saket Saurabh, Yngve Villanger
Title : A Polynomial kernel for Proper Interval Vertex Deletion
In : Proceedings of 20th European Symposium on Algorithms (ESA 2012), LNCS -
Address :
Date : 2012
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen - Induced Disjoint Paths in Claw-Free Graphs
Proceedings of 20th European Symposium on Algorithms (ESA 2012), LNCS 7501:515-526,2012
http://arxiv.org/abs/1202.4419
Bibtex
Author : Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
Title : Induced Disjoint Paths in Claw-Free Graphs
In : Proceedings of 20th European Symposium on Algorithms (ESA 2012), LNCS -
Address :
Date : 2012
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström - Clique Cover and Graph Separation: New Incompressibility Results
Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), track A, LNCS 7391:254-265,2012
http://arxiv.org/abs/1111.0570
Bibtex
Author : Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström
Title : Clique Cover and Graph Separation: New Incompressibility Results
In : Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), track A, LNCS -
Address :
Date : 2012
Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström - Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), track A, LNCS 7391:581-593,2012
http://arxiv.org/abs/1202.5749
Bibtex
Author : Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström
Title : Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
In : Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), track A, LNCS -
Address :
Date : 2012
Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michał Pilipczuk - Minimizing Rosenthal Potential in Multicast Games
Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), track C, LNCS 7392:535-536,2012
Pdf http://www.springerlink.com/content/u2134702514j7303/
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michał Pilipczuk
Title : Minimizing Rosenthal Potential in Multicast Games
In : Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), track C, LNCS -
Address :
Date : 2012
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk - Sitting closer to friends than enemies, revisited
Proceedings of 37th International Symposium on Mathematical Foundations of Computer Sciences (MFCS 2012), LNCS 7464:455-466,2012
http://arxiv.org/abs/1201.1869
Bibtex
Author : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Title : Sitting closer to friends than enemies, revisited
In : Proceedings of 37th International Symposium on Mathematical Foundations of Computer Sciences (MFCS 2012), LNCS -
Address :
Date : 2012
Petr A. Golovach, Pim Van 'T Hof, Daniël Paulusma - Obtaining planarity by contracting few edges
Proceedings of 37th International Symposium on Mathematical Foundations of Computer Sciences (MFCS 2012), LNCS 7464:455-466,2012
Pdf http://www.springerlink.com/content/u2134702514j7303/
Bibtex
Author : Petr A. Golovach, Pim Van 'T Hof, Daniël Paulusma
Title : Obtaining planarity by contracting few edges
In : Proceedings of 37th International Symposium on Mathematical Foundations of Computer Sciences (MFCS 2012), LNCS -
Address :
Date : 2012
Petr A. Golovach, Dani\"el Paulusma, Bernard Ries - Coloring Graphs Characterized by a Forbidden Subgraph
Proceedings of 37th International Symposium on Mathematical Foundations of Computer Sciences (MFCS 2012), LNCS 7464:443-454,2012
Bibtex
Author : Petr A. Golovach, Dani\"el Paulusma, Bernard Ries
Title : Coloring Graphs Characterized by a Forbidden Subgraph
In : Proceedings of 37th International Symposium on Mathematical Foundations of Computer Sciences (MFCS 2012), LNCS -
Address :
Date : 2012
Fedor V. Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger - k-Gap Interval Graphs
Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN 2012), LNCS 7256:350-361,2012
Pdf http://www.springerlink.com/content/702787k88kt08316/
Bibtex
Author : Fedor V. Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger
Title : k-Gap Interval Graphs
In : Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN 2012), LNCS -
Address :
Date : 2012
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk - Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2^n
Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN 2012), LNCS 7256:195-206,2012
Pdf http://dx.doi.org/10.1007/978-3-642-29344-3_17
Bibtex
Author : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Title : Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2^n
In : Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN 2012), LNCS -
Address :
Date : 2012
Fedor V. Fomin, Petr A. Golovach - Parameterized Complexity of Connected Even/Odd Subgraph Problems
Proceedings of 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) 14:432-440,2012
Pdf http://drops.dagstuhl.de/opus/volltexte/2012/3398/
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach
Title : Parameterized Complexity of Connected Even/Odd Subgraph Problems
In : Proceedings of 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) -
Address :
Date : 2012
Fedor V. Fomin, Yngve Vilanger - Subexponential Parameterized Algorithm for Minimum Fill-in
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) pp. 1737--1746,2012
Pdf http://arxiv.org/abs/1104.2230
Bibtex
Author : Fedor V. Fomin, Yngve Vilanger
Title : Subexponential Parameterized Algorithm for Minimum Fill-in
In : Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) -
Address :
Date : 2012
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh - Bidimensionality and geometric graphs
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) pp. 1563-1575,2012
http://arxiv.org/abs/1107.2221
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh
Title : Bidimensionality and geometric graphs
In : Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) -
Address :
Date : 2012
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos - Linear kernels for (connected) dominating set on {H}-minor-free graphs
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) pp. 82-93,2012
http://www.ii.uib.no/~daniello/papers/domsetHMinorFree.pdf
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos
Title : Linear kernels for (connected) dominating set on {H}-minor-free graphs
In : Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) -
Address :
Date : 2012

2011

Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen - Parameterized complexity of firefighting revisited
Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC 2011), LNCS 7112:13--26,2011
http://arxiv.org/abs/1109.4729
Bibtex
Author : Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
Title : Parameterized complexity of firefighting revisited
In : Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC 2011), LNCS -
Address :
Date : 2011
Fedor V. Fomin, Geevarghese Philip, Yngve Villanger - Minimum fill-in of sparse graphs: Kernelization and approximation
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) 13:164-175,2011
http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.164
Bibtex
Author : Fedor V. Fomin, Geevarghese Philip, Yngve Villanger
Title : Minimum fill-in of sparse graphs: Kernelization and approximation
In : IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) -
Address :
Date : 2011

Journals

2016

Hans L. Bodlaender, P\aal Gr\on\aas Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk - A c\({}^{\mbox{k}}\) n 5-Approximation Algorithm for Treewidth
{SIAM} J. Comput. 45(2):317--378,2016
http://dx.doi.org/10.1137/130947374
Bibtex
Author : Hans L. Bodlaender, P\aal Gr\on\aas Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk
Title : A c\({}^{\mbox{k}}\) n 5-Approximation Algorithm for Treewidth
In : {SIAM} J. Comput. -
Address :
Date : 2016
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk - Known Algorithms for Edge Clique Cover are Probably Optimal
{SIAM} J. Comput. 45(1):67--83,2016
http://dx.doi.org/10.1137/130947076
Bibtex
Author : Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
Title : Known Algorithms for Edge Clique Cover are Probably Optimal
In : {SIAM} J. Comput. -
Address :
Date : 2016
Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach - Parameterized complexity of the anchored k-core problem for directed graphs
Inf. Comput. 247:11--22,2016
http://dx.doi.org/10.1016/j.ic.2015.11.002
Bibtex
Author : Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach
Title : Parameterized complexity of the anchored k-core problem for directed graphs
In : Inf. Comput. -
Address :
Date : 2016
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh - Hitting Forbidden Minors: Approximation and Kernelization
{SIAM} J. Discrete Math. 30(1):383--410,2016
http://dx.doi.org/10.1137/140997889
Bibtex
Author : Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh
Title : Hitting Forbidden Minors: Approximation and Kernelization
In : {SIAM} J. Discrete Math. -
Address :
Date : 2016

2015

Fedor V. Fomin, Geevarghese Philip, Yngve Villanger - Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
Algorithmica 71(1):1--20,2015
http://dx.doi.org/10.1007/s00453-013-9776-1
Bibtex
Author : Fedor V. Fomin, Geevarghese Philip, Yngve Villanger
Title : Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
In : Algorithmica -
Address :
Date : 2015
Fedor V. Fomin, Ioan Todinca, Yngve Villanger - Large Induced Subgraphs via Triangulations and {CMSO}
{SIAM} J. Comput. 44(1):54--87,2015
http://dx.doi.org/10.1137/140964801
Bibtex
Author : Fedor V. Fomin, Ioan Todinca, Yngve Villanger
Title : Large Induced Subgraphs via Triangulations and {CMSO}
In : {SIAM} J. Comput. -
Address :
Date : 2015
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk - A Subexponential Parameterized Algorithm for Proper Interval Completion
{SIAM} J. Discrete Math. 29(4):1961--1987,2015
http://dx.doi.org/10.1137/140988565
Bibtex
Author : Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk
Title : A Subexponential Parameterized Algorithm for Proper Interval Completion
In : {SIAM} J. Discrete Math. -
Address :
Date : 2015
Henning Fernau, Fedor V. Fomin, Geevarghese Philip, Saket Saurabh - On the parameterized complexity of vertex cover and edge cover with connectivity constraints
Theor. Comput. Sci. 565:1--15,2015
http://dx.doi.org/10.1016/j.tcs.2014.10.035
Bibtex
Author : Henning Fernau, Fedor V. Fomin, Geevarghese Philip, Saket Saurabh
Title : On the parameterized complexity of vertex cover and edge cover with connectivity constraints
In : Theor. Comput. Sci. -
Address :
Date : 2015


Fedor V. Fomin, Archontia C. Giannopoulou, Michal Pilipczuk - Computing Tree-Depth Faster Than 2\({}^{\mbox{n}}\)
Algorithmica 73(1):202--216,2015
http://dx.doi.org/10.1007/s00453-014-9914-4
Bibtex
Author : Fedor V. Fomin, Archontia C. Giannopoulou, Michal Pilipczuk
Title : Computing Tree-Depth Faster Than 2\({}^{\mbox{n}}\)
In : Algorithmica -
Address :
Date : 2015


Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlstr\"om - Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
{SIAM} J. Discrete Math. 29(1):122--144,2015
http://dx.doi.org/10.1137/120904202
Bibtex
Author : Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlstr\"om
Title : Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
In : {SIAM} J. Discrete Math. -
Address :
Date : 2015
Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michal Pilipczuk - Minimizing Rosenthal Potential in Multicast Games
Theory Comput. Syst. 57(1):81--96,2015
http://dx.doi.org/10.1007/s00224-014-9573-5
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michal Pilipczuk
Title : Minimizing Rosenthal Potential in Multicast Games
In : Theory Comput. Syst. -
Address :
Date : 2015
Petr A. Golovach, Daniel Paulusma, Erik Jan van Leeuwen - Induced Disjoint Paths in Claw-Free Graphs
{SIAM} J. Discrete Math. 29(1):348--375,2015
http://dx.doi.org/10.1137/140963200
Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Erik Jan van Leeuwen
Title : Induced Disjoint Paths in Claw-Free Graphs
In : {SIAM} J. Discrete Math. -
Address :
Date : 2015

Hajo Broersma, Jiri Fiala, Petr A. Golovach, Tomas Kaiser, Daniel Paulusma, Andrzej Proskurowski - Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity

of Interval Graphs
Journal of Graph Theory 79(4):282--299,2015
http://dx.doi.org/10.1002/jgt.21832
Bibtex
Author : Hajo Broersma, Jiri Fiala, Petr A. Golovach, Tomas Kaiser, Daniel Paulusma, Andrzej Proskurowski
Title : Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
In : Journal of Graph Theory -
Address :
Date : 2015
Petr A. Golovach, Daniel Paulusma, Bernard Ries - Coloring graphs characterized by a forbidden subgraph
Discrete Applied Mathematics 180:101--110,2015
http://dx.doi.org/10.1016/j.dam.2014.08.008
Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Bernard Ries
Title : Coloring graphs characterized by a forbidden subgraph
In : Discrete Applied Mathematics -
Address :
Date : 2015
Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniel Paulusma, Michal Pilipczuk - Modifying a Graph Using Vertex Elimination
Algorithmica 72(1):99--125,2015
http://dx.doi.org/10.1007/s00453-013-9848-2
Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniel Paulusma, Michal Pilipczuk
Title : Modifying a Graph Using Vertex Elimination
In : Algorithmica -
Address :
Date : 2015

2014

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh - Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
SIAM J. Comput. 43(5):1541--1563,2014
http://dx.doi.org/10.1137/130910932
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh
Title : Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
In : SIAM J. Comput. -
Address :
Date : 2014
Peter Biro, Matthijs Bomhoff, Petr A. Golovach, Walter Kern, Daniel Paulusma - Solutions for the stable roommates problem with payments
Theor. Comput. Sci. 540:53--61,2014
http://dx.doi.org/10.1016/j.tcs.2013.03.027
Bibtex
Author : Peter Biro, Matthijs Bomhoff, Petr A. Golovach, Walter Kern, Daniel Paulusma
Title : Solutions for the stable roommates problem with payments
In : Theor. Comput. Sci. -
Address :
Date : 2014

Remy Belmonte, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma - Parameterized complexity of three edge contraction problems with degree

constraints
Acta Inf. 51(7):473--497,2014
http://dx.doi.org/10.1007/s00236-014-0204-z
Bibtex
Author : Remy Belmonte, Petr A. Golovach, Pim van 't Hof, Daniel Paulusma
Title : Parameterized complexity of three edge contraction problems with degree constraints
In : Acta Inf. -
Address :
Date : 2014
Petr A. Golovach, Daniel Paulusma - List coloring in the absence of two subgraphs
Discrete Applied Mathematics 166:123--130,2014
http://dx.doi.org/10.1016/j.dam.2013.10.010
Bibtex
Author : Petr A. Golovach, Daniel Paulusma
Title : List coloring in the absence of two subgraphs
In : Discrete Applied Mathematics -
Address :
Date : 2014
Petr A. Golovach, Daniel Paulusma, Jian Song - Coloring graphs without short cycles and long induced paths
Discrete Applied Mathematics 167:107--120,2014
http://dx.doi.org/10.1016/j.dam.2013.12.008
Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Jian Song
Title : Coloring graphs without short cycles and long induced paths
In : Discrete Applied Mathematics -
Address :
Date : 2014
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey - Finding clubs in graph classes
Discrete Applied Mathematics 174:57--65,2014
http://dx.doi.org/10.1016/j.dam.2014.04.016
Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey
Title : Finding clubs in graph classes
In : Discrete Applied Mathematics -
Address :
Date : 2014
Petr A. Golovach, Daniel Paulusma, Jian Song - Closing complexity gaps for coloring problems on H-free graphs
Inf. Comput. 237:204--214,2014
http://dx.doi.org/10.1016/j.ic.2014.02.004
Bibtex
Author : Petr A. Golovach, Daniel Paulusma, Jian Song
Title : Closing complexity gaps for coloring problems on H-free graphs
In : Inf. Comput. -
Address :
Date : 2014
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei - Subset feedback vertex sets in chordal graphs
J. Discrete Algorithms 26:7--15,2014
http://dx.doi.org/10.1016/j.jda.2013.09.005
Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
Title : Subset feedback vertex sets in chordal graphs
In : J. Discrete Algorithms -
Address :
Date : 2014
Konrad Dabrowski, Petr A. Golovach, Daniel Paulusma - Colouring of graphs with Ramsey-type forbidden subgraphs
Theor. Comput. Sci. 522:34-43,2014
Bibtex
Author : Konrad Dabrowski, Petr A. Golovach, Daniel Paulusma
Title : Colouring of graphs with Ramsey-type forbidden subgraphs
In : Theor. Comput. Sci. -
Address :
Date : 2014
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter - Parameterized Complexity of Eulerian Deletion Problems
Algorithmica 68(1):41-61,2014
Bibtex
Author : Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter
Title : Parameterized Complexity of Eulerian Deletion Problems
In : Algorithmica -
Address :
Date : 2014
Fedor V. Fomin, Petr A. Golovach - Parameterized complexity of connected even/odd subgraph problems
J. Comput. Syst. Sci. 80(1):157-179,2014
Bibtex
Author : Fedor V. Fomin, Petr A. Golovach
Title : Parameterized complexity of connected even/odd subgraph problems
In : J. Comput. Syst. Sci. -
Address :
Date : 2014
Fedor V. Fomin, Bart M.P. Jansen, Michał Pilipczuk - Preprocessing subgraph and minor problems: When does a small vertex cover help?
Journal of Computer and System Sciences 80(2):468 - 495,2014
http://www.sciencedirect.com/science/article/pii/S0022000013001682
Bibtex
Author : Fedor V. Fomin, Bart M.P. Jansen, Michał Pilipczuk
Title : Preprocessing subgraph and minor problems: When does a small vertex cover help?
In : Journal of Computer and System Sciences -
Address :
Date : 2014

2013

Fedor V. Fomin, Saket Saurabh, Yngve Villanger - A polynomial kernel for Proper Interval Vertex Deletion
SIAM J. Discrete Math. 27(4):1964-1976,2013
Bibtex
Author : Fedor V. Fomin, Saket Saurabh, Yngve Villanger
Title : A polynomial kernel for Proper Interval Vertex Deletion
In : SIAM J. Discrete Math. -
Address :
Date : 2013
Fedor V. Fomin, Yngve Villanger - Subexponential parameterized algorithm for Minimum Fill-In
SIAM J. Comput. 42(6):2197-2216,2013
Bibtex
Author : Fedor V. Fomin, Yngve Villanger
Title : Subexponential parameterized algorithm for Minimum Fill-In
In : SIAM J. Comput. -
Address :
Date : 2013
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk - On multiway cut parameterized above lower bounds
TOCT 5(1):3,2013
Bibtex
Author : Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
Title : On multiway cut parameterized above lower bounds
In : TOCT -
Address :
Date : 2013
Petr A. Golovach, Dieter Kratsch, Daniel Paulusma - Detecting induced minors in AT-free graphs
Theor. Comput. Sci. 482:20-32,2013
Pdf Bibtex
Author : Petr A. Golovach, Dieter Kratsch, Daniel Paulusma
Title : Detecting induced minors in AT-free graphs
In : Theor. Comput. Sci. -
Address :
Date : 2013
Hajo Broersma, Petr A. Golovach, Viresh Patel - Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
Theor. Comput. Sci. 485:69-84,2013
Pdf Bibtex
Author : Hajo Broersma, Petr A. Golovach, Viresh Patel
Title : Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
In : Theor. Comput. Sci. -
Address :
Date : 2013
Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Daniel Paulusma - Choosability on H-free graphs
Inf. Process. Lett. 113(4):107-110,2013
Pdf Bibtex
Author : Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Daniel Paulusma
Title : Choosability on H-free graphs
In : Inf. Process. Lett. -
Address :
Date : 2013
Petr A. Golovach, Pim van 't Hof, Daniel Paulusma - Obtaining planarity by contracting few edges
Theor. Comput. Sci. 476:38-46,2013
Pdf Bibtex
Author : Petr A. Golovach, Pim van 't Hof, Daniel Paulusma
Title : Obtaining planarity by contracting few edges
In : Theor. Comput. Sci. -
Address :
Date : 2013
Fedor V. Fomin, Petteri Kaski - Exact exponential algorithms
Commun. ACM 56(3):80-88,2013
Bibtex
Author : Fedor V. Fomin, Petteri Kaski
Title : Exact exponential algorithms
In : Commun. ACM -
Address :
Date : 2013

2012

Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger - Kernel(s) for problems with no kernel: On out-trees with many leaves
ACM Transactions on Algorithms 8(4):38,2012
Bibtex
Author : Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger
Title : Kernel(s) for problems with no kernel: On out-trees with many leaves
In : ACM Transactions on Algorithms -
Address :
Date : 2012

Book Chapters

2014

Fedor V. Fomin, saket Saurabh - Kernelization methods for fixed-parameter tractability,
Tractability 7370:260-280,2014
Pdf Bibtex
Author : Fedor V. Fomin, saket Saurabh
Title : Kernelization methods for fixed-parameter tractability,
In : Tractability -
Address :
Date : 2014

2012

Fedor V. Fomin, Dániel Marx - FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, LNCS 7370:457-468,2012
Pdf http://dx.doi.org/10.1007/978-3-642-30891-8_19
Bibtex
Author : Fedor V. Fomin, Dániel Marx
Title : FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
In : The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, LNCS -
Address :
Date : 2012