Events
From preprocessing
2016
- 11.02 Paper "Subexponential algorithms for rectilinear Steiner tree and arborescence problems" by Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh has been accepted at SoCG 2016
- 02.02 Paper "Exact Algorithms via Monotone Local Search" by Fedor Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh has been accepted at STOC 2016
2015
- 02.11 Fedor Fomin gave talk on Fine-Grained Complexity of Exact Algorithms and and Petr Golovach on Lower Bounds for Problems Parameterized by Clique-width at Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms workshop
- 20.09 Papers "Editing to Connected f -Degree Graph" by Fedor Fomin, Petr Golovach, Fahad Panolan and Saket Saurabh and "Kernelization and Sparseness: the case of Dominating Set" by Pål Grønås Drange, Markus Dregi, Fedor Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sanchez Villaamil, Saket Saurabh, Sebastian Siebertz and Somnath Sikdar have been accepted at STACS 2016
- 20.09 Papers "Subexponential parameterized algorithm for Interval Completion" by Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk and Michal Pilipczuk and "Tight Bounds for Subgraph Isomorphism and Graph Homomorphism" by Fedor Fomin, Alexander Golovnev, Alexander Kulikov and Ivan Mihajlin have been accepted at SODA 2016
- 16-19.06 Petr Golovach participated at the Algorithmic Graph Theory on Adriatic Coast workshop (AGTAC 2015) and gave a talk "Parameterized Complexity of Secluded Connectivity Problems".
- 17.06 Two papers, A Polynomial Kernel for Trivially Perfect Editing by Pål Grønås Drange and Michał Pilipcuk, and On the Threshold of Intractability by Pål Grønås Drange, Markus Dregi, Daniel Lokshtanov, and Blair D. Sullivan have been accepted to ESA 2015.
- 05.06 Paper "Metric Dimension of Bounded Width Graphs" by Ramanujan M. S., Petr Golovach, Fedor Fomin and Remy Belmonte have been accepted to MFCS 2015.
- 31.05–04.06 Worker 2015 — Workshop on Kernelization was organized by Pål Grønås Drange (chair) and Fedor V. Fomin, together with Markus Dregi, Daniel Lokshtanov, Dániel Marx and Saket Saurabh. The workshop contained six tutorials and twelve contributed talks. (Proceedings)
- 26-28.05 Petr Golovach participated at 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, Istanbul, Turkey May 26-28, 2015 (CTW 2015) and gave a talk "How to hunt an invisible rabbit on a graph".
- 14.04 Papers “Parameterized single-exponential time polynomial space algorithm for Steiner Tree” by Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh, “Lower Bounds for the Graph Homomorphism Problem” by Fedor V. Fomin, Alexander Golovnev, Alexander Kulikov and Ivan Mihajlin, and “Deterministic Truncation of Linear Matroids” by Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan and Saket Saurabh have been accepted at ICALP 2015
- 10.04 Papers "On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids" by Fahad Panolan, Ramanujan M. S. and Saket Saurabh and "Reconfiguration on sparse graphs" by Daniel Lokshtanov, Amer Mouawad, Fahad Panolan, M.S. Ramanujan and Saket Saurabh have been accepted at WADS 2015
- 24.03 Paper “Parameterized complexity of superstring problems” by Ivan Bliznets, Fedor V. Fomin, Petr Golovach, Nikolay Karpov, Alexander Kulikov and Saket Saurabh has been accepted at CPM 2015
- 01.03–01.05 Pål Grønås Drange visited NICTA/UNSW, Sydney, Australia
- 15.02 Paper "Editing to a planar graph of given degrees" by Konrad Kazimierz Dabrowski, Petr Golovach, Pim Van 'T Hof, Daniel Paulusma and Dimitrios Thilikos have been accepted to CSR 2015.
- 21.01 Pål Grønås Drange presented On the square root phenomenon in graph modification problems at NICTA/UNSW, Sydney, Australia
- 21.01 Pål Grønås Drange presented On the Computational Complexity of Threshold Editing at the International Workshop on Graph Decomposition, Marseilles, France
2014
- 15.12 Pål Grønås Drange presented On the Computational Complexity of Vertex Integrity and Component Order Connectivity at ISAAC, Jeonju, South-Korea.
- 17.09 Michał Pilipczuk receives a nomination to the International Stefan Banach Prize for his doctoral dissertation.
- 13.09 Papers "Connecting Vertices by Independent Trees" by Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh and "Editing to Eulerian Graphs" by Konrad K. Dabrowski, Petr A. Golovach, Pim Van 'T Hof and D. Paulusma have been accepted at FSTTCS 2014
- 09.09 Paper "Solving d-SAT via Backdoors to Small Treewidth" by Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, and Saket Saurabh has been accepted at SODA 2015
- 08-12.09 Petr A. Golovach and Michał Pilipczuk participated in ALGO 2014. Petr gave a talk on "Editing to a Graph of Given Degrees" at IPEC 2014 and Michał gave talks on "A subexponential parameterized algorithm for Proper Interval Completion" and "Representative Sets of Product Families" at ESA 2014
- 25-29.08 Petr A. Golovach and Michał Pilipczuk participated in MFCS 2014. Petr gave a talk on "Editing to a Connected Graph of Given Degrees" and Michał gave a talk on "Hitting forbidden subgraphs in graphs of bounded treewidth".
- 26.08 Fahad Panolan joined the project
- 17.08-22.08 School on Parameterized Algorithms
- 11.08 Article in Hubro about Michal's research
- 08-11.07 Manu Basavaraju participated in ICALP 2014, Manu presented the paper "Parameterized Algorithms to Preserve Connectivity" co-authored by Fedor Fomin, and Petr Golovach, Pranabendu Misra, M. S. Ramanujan and Saket Saurabh.
- 31.06-04.07 Manu Basavaraju participated in ICGT 2014, Manu presented the paper "Separation dimension of sparse graphs" co-auhtored by L. Sunil Chandran, Rogers Mathew, and Deepak Rajendraprasad.
- 01.07 Papers "Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs" by Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen and "Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth" by Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, have been accepted at FOCS 2014
- 17.06 Papers "A subexponential parameterized algorithm for Proper Interval Completion" by Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk and Michał Pilipczuk, "Representative Sets of Product Families" by Fedor Fomin, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh, and "The Parameterized Complexity of Graph Cyclability" by Petr Golovach, Marcin Kamiński, Spyridon Maniatis and Dimitrios Thilikos have been accepted at ESA 2014
- 04.06 Papers "Hitting forbidden subgraphs in graphs of bounded treewidth" by Marek Cygan, Daniel Marx, Marcin Pilipczuk and Michal Pilipczuk and "Editing to a connected graph of given degrees" by Petr Golovach have been accepted at MFCS 2014
- 19.05 – 22.05 mini-school "Grid Theorem" with Chandra Chekuri.
- 24.04 Pål Grønås Drange presented "Parameterized Complexity A Primer" at the Workshop in honor of Workshop in Honour of Hans Birger Drange on His 70th Birthday, at Høyskolen i Bergen, Norway
- 22.04 Papers "Boxicity and Separation Dimension " by Manu Basavaraju, L. Sunil Chandran, Martin C. Golumbic, Rogers Mathew and Deepak Rajendraprasad and " Maximal induced matchings in triangle-free graphs" by Manu Basavaraju, Pinar Heggernes, Pim Van't Hof, Reza Saei and Yngve Villanger have been accepted at WG 2014
- 22.04 Papers "Hadwiger number of graphs with small chordality" by Petr Golovach, Pinar Heggernes, Pim Van't Hof and Christophe Paul and " Induced disjoint paths in circular-arc graphs in linear time" by Petr Golovach, Daniel Paulusma and Erik Jan van Leeuwen have been accepted at WG 2014
- 14.04 Paper "Algorithms parameterized by vertex cover and modular width, through potential maximal cliques" by Fedor Fomin, Mathieu Liedloff, Pedro Montealegre, and Ioan Todinca has been accepted at SWAT 2014
- 12.04 Paper "Parameterized Algorithms to Preserve Connectivity" by Ramanujan M. S., Saket Saurabh, Pranabendu Misra, Manu Basavaraju, Fedor Fomin, and Petr Golovach has been accepted at ICALP 2014
- 07.03 Michał Pilipczuk receives Meltzer prize for young researchers for his work in the project.
- 06-08.03 Pål Grønås Drange and Michał Pilipczuk participated in STACS 2014, ENS Lyon, France. Michał presented "Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)" and Pål presented "Exploring Subexponential Parameterized Complexity of Completion Problems".
- 06.03 Pål Grønås Drange co-organized "Fagdag" at the Department of Informatics [1] [2]
- 09-14.02 Petr A. Golovach, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk participated in Dagstuhl seminar 14071 on graph modification problems. Marcin and Michał gave a talk on "Subexponential parameterized algorithms for completion problems", and Petr gave a talk on " Editing to a connected graph of given degrees".
- 05.02 Paper "Minimum Bisection is fixed-parameter tractable" by Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, has been accepted at STOC 2014
2013
- 15.12 Article in Hubro about the Algorithms group
- 15-20.12 Marcin and Michał Pilipczuk participated in Bertinoro Workshop on Algorithms and Graphs. Marcin gave a talk on "Network sparsification for Steiner problems on planar and bounded genus graphs", and Michał gave a talk on "Minimum Bisection is fixed-parameter tractable".
- 11.12 Article about Michał's work in UiB news
- 08.12 Papers "Exploring Subexponential Parameterized Complexity of Completion Problems" by Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk and Yngve Villanger and "Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)" by Dániel Marx and Michał Pilipczuk accepted at STACS 2014.
- 22.11 Michał Pilipczuk successfully defended PhD thesis "Tournaments and optimality: new results in fixed-parameter tractability".
- 01.11 Paper "Synthesizing transformations from XML schema mappings" by Claire David, Piotr Hofman, Filip Murlak, and Michał Pilipczuk, has been accepted at ICDT 2014.
- 26.10-29.10 Pål Grønås Drange, Fedor V. Fomin and Michał Pilipczuk participated in FOCS 2013. Fedor gave a tutorial on "Advanced Bidimensionality and Its Applications" on a pre-conference workshop devoted to bidimensionality and Michał gave a talk on "The k-Disjoint Paths problem in directed planar graphs".
- 13.10-17.10 Petr Golovach, Marcin Pilipczuk and Michał Pilipczuk participated in Dagstuhl seminar 13421 "Algorithms for Optimization Problems in Planar Graphs". Marcin gave a talk on "Network sparsification for Steiner problems on planar and bounded-genus graphs" and Michał gave a talk on "The k-Disjoint Paths problem in directed planar graphs".
- 09-11.10 Pål Grønås Drange, Archontia C. Giannopoulou, Marcin Pilipczuk, and Michał Pilipczuk participated in GROW 2013. Archontia was one of the organizers of the event. Marcin gave a talk on "The k-Disjoint Paths problem in directed planar graphs" and Michał gave a talk on "Topological problems in tournaments".
- 05.10 Pål Grønås Drange and Michał Pilipczuk organized and were problem setters for NCPC 2013 – Nordic Collegiate Programming Contest
- 01.10 Article in Hubro about Algorithms group
- 17-19.09 Marcin Pilipczuk participated in 5th Forum of Polish Mathematicians, where he gave a talk on "Random contractions, balanced cuts and graph separation problems"
- 18.09 Papers "Large induced subgraphs via triangulations and CMSO" by Fedor V. Fomin, Ioan Todinca, and Yngve Villanger and "Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms" by Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh have been accepted at SODA 2014
- 02-06.09 Petr A. Golovach and Michał Pilipczuk participated in ALGO 2013, a conference panel hosting, among others, ESA 2013 and IPEC 2013. Petr gave a talk on "Long Circuits and Large Euler Subgraphs" during ESA 2013, co-authored by Fedor V. Fomin. Michał gave a talk on "Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph" during ESA 2013, co-authored by Fedor V. Fomin, as well as on "Computing Tree-depth Faster Than 2^n" during IPEC 2013, co-authored by Fedor V. Fomin and Archontia C. Giannopoulou.
- 10-15.08 Fedor V. Fomin participated in Dagstuhl seminar 13331 "Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time".
- 08.08 Marcin Pilipczuk joined the project
- 13.07 Papers "Faster Exact Algorithms for Some Terminal Set Problems" by Fedor V. Fomin, Daniel Lokshtanov, Rajesh Chitnis, Pranabendu Misra, Ramanujan M. S., Saket Saurabh, "Computing Tree-depth Faster Than 2^n" by Fedor V. Fomin, Archontia C. Giannopoulou, and Michał Pilipczuk, "Parameterized complexity of two edge contraction problems with degree constraints" by Remy Belmonte, Petr A. Golovach, Pim van 't Hof, and Daniël Paulusma have been accepted at IPEC 2013.
- 27.06 Papers "The planar directed k-‐Vertex-‐Disjoint Paths problem is fixed-‐parameter tractable" by Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk and "An O(c^k) n 5-‐Approximation Algorithm for Treewidth", by Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michał Pilipczuk have been accepted at FOCS 2013.
- 08-12.07 Fedor V. Fomin and Petr A. Golovach participated in ICALP 2013. Petr gave a talk on "An incremental polynomial time algorithm to enumerate all minimal edge dominating sets" co-authored by Pinar Heggernes, Dieter Kratsch and Yngve Villanger.
- 19-21.06 Fedor V. Fomin, Archontia C. Giannopoulou, and Petr Golovach participated in WG 2013. Petr gave a talk on "Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs" co-authored by Hajo Broersma, Jiri Fiala, Tomas Kaiser, Daniel Paulusma and Andrzej Proskurowski and Archontia gave a talk on "Excluding graphs as immersions in surface embedded graphs" co-authored by Marcin Kaminski and Dimitrios Thilikos.
- 10.06 Papers "Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph" by Fedor Fomin and Michał Pilipczuk, "Long Circuits and Large Euler Subgraphs" by Fedor Fomin and Petr Golovach, and "Largest chordal and interval subgraphs faster than 2^n" by Ivan Bliznets, Fedor Fomin, Michał Pilipczuk and Yngve Villanger have been accepted at ESA 2013.
- 02.06 Paper "On the parameterized complexity of cutting a few vertices from a graphs" by Fedor Fomin, Petr Golovach and Janne H. Korhonen has been accepted at MFCS 2013.
- 23.05 Petr Golovach gave a talk on the paper "List Coloring in the Absence of Two Subgraphs", co-authored by Daniel Paulusma, at CIAC 2013
- 05-10.05 Fedor Fomin participated in PARAMETERIZED COMPLEXITY AND THE UNDERSTANDING, DESIGN AND ANALYSIS OF HEURISTICS, NII Shonan Meeting Seminar 018 and gave a talk on "Parameterized k-opt"
- 30.04 Papers "Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs" by Hajo Broersma, Jiri Fiala, Petr Golovach, Tomas Kaiser, Daniel Paulusma and Andrzej Proskurowski, "Excluding graphs as immersions in surface embedded graphs" by Archontia C. Giannopoulou, Marcin Kamiński and Dimitrios M. Thilikos, "Colouring of graphs with Ramsey-type forbidden subgraphs" by Konrad Dabrowski, Petr Golovach and Daniel Paulusma, and "Sparse square roots" by Manfred Cochefert, Jean-François Couturier, Petr Golovach, Dieter Kratsch and Daniel Paulusma have been accepted at WG 2013.
- 25.04 Pål Grønås Drange, Daniel Lokshtanov and Markus S. Dregi had a popular scientific poster stand at the Christiekonferansen.
- 09-12.04 Pål Grønås Drange, Fedor V. Fomin, Archontia C. Giannopoulou, Petr Golovach and Michał Pilipczuk participated in Workshop on Kernels 2013. Michał gave a talk on "Randomized Contractions".
- 12.04 Paper "An incremental polynomial time algorithm to enumerate all minimal edge dominating sets" by Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger is accepted at 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
- 26.03 Paper "Preventing Unraveling in Social Networks Gets Harder" by Rajesh Chitnis, Fedor Fomin, and Petr Golovach is accepted to Artificial Intelligence and the Web Track at the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13)
- 21.03 Pål Grønås Drange organized a Horisonter lecture (part of the Faculty of Mathematics and Natural Sciences lecture series) with Jo Røislien as guest speaker.
- 17-22.03 Fedor V. Fomin, Archontia C. Giannopoulou, Petr Golovach and Michał Pilipczuk participated in Dagstuhl seminar 13121 "Bidimensional Structures: Algorithms, Combinatorics and Logic". Michał gave a talk on "Topological problems in tournaments" and Archontia gave a talk on "Exclusion theorems for immersions on surface embedded graphs".
- 11.03 – 12.03 Pål Grønås Drange organized the ICT Research School 2013, a research school for PhD students in the Department of Informatics at UiB.
- 05.03 Manu Basavaraju joined the project
- 28.02 Michał Pilipczuk gave a talk on paper "Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings", at STACS 2013
- 28.02 Michał Pilipczuk gave a talk on paper "Tight bounds for parameterized complexity of cluster editing", co-authored by Fedor V. Fomin, Stefan Kratsch, Yngve Villanger and Marcin Pilipczuk, at STACS 2013
- 19-22.02 Winter School in Algorithm
- 08.01 Michał Pilipczuk gave a talk on paper "Known algorithms for Edge Clique Cover are probably optimal", co-authored by Marek Cygan and Marcin Pilipczuk, at SODA 2013
- 07.01 Michał Pilipczuk gave a talk on paper "Jungles, bundles, and fixed-parameter tractability", co-authored by Fedor V. Fomin, at SODA 2013
2012
- 19.12 and 21.12 Petr Golovach gave talks on the papers "Closing Complexity Gaps for Coloring Problems on H-Free Graphs" co-authored by Daniël Paulusma and Jian Song and "Detecting Induced Minors in AT-free Graphs" co-authored by Dieter Kratsch and Daniël Paulusma at ISAAC 2012
- 08.12 Papers "Tight bounds for parameterized complexity of cluster editing" by Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Yngve Villanger, "Searching for better fill-in" by Fedor Fomin and Yngve Villanger, "Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs" by Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos, "Subexponential-time parameterized algorithm for steiner tree on planar graphs" by Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen, and "Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings" by Michał Pilipczuk have been accepted to STACS 2013
- 01.12 Archontia C. Giannopoulou joined the project
- 03.11 Fedor Fomin gave a talk on "Subexponential algorithms for fill-in" co-authored by Yngve Villanger at Graph Theory 2012
- 06.10 Pål Grønås Drange and Michał Pilipczuk organized and were problem setters for NCPC 2012 – Nordic Collegiate Programming Contest
- 24-25.09 Fedor Fomin gave a tutorial on Exact and parameterized algorithms at ENUMEX 2012
- 13.09 Michał Pilipczuk gave a tutorial on lower bounds for polynomial kernelization during IPEC 2012
- 13.09 Fedor Fomin gave a talk on paper "Preprocessing subgraph and minor problems: When does a small vertex cover help?", co-authored by Bart Jansen and Michał Pilipczuk, at IPEC 2012
- 12.09 Michał Pilipczuk gave a talk on paper "Finding maximum induced degenerate subgraph faster than 2^n", co-authored by Marcin Pilipczuk, at IPEC 2012
- 07.09 Papers "Jungles, bundles, and fixed-parameter tractability" by Fedor V. Fomin and Michał Pilipczuk, and "Known algorithms for Edge Clique Cover are probably optimal" by Marek Cygan, Marcin Pilipczuk and Michał Pilipczuk have been accepted at SODA 2013
- 31.08 Michał Pilipczuk gave a talk on paper "Sitting closer to friends than enemies, revisited", co-authored by Marek Cygan, Marcin Pilipczuk and Jakub Onufry Wojtaszczyk, at MFCS 2012
- 24.07 Papers " Detecting Induced Minors in AT-free Graphs" by Petr Golovach, Dieter Kratsch and Daniël Paulusma, and "Closing Complexity Gaps for Coloring Problems on H-Free Graphs" by Petr Golovach, Daniël Paulusma and Jian Song have been accepted at ISAAC 2012
- 14.07 Papers "Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?" by Fedor V. Fomin, Bart Jansen and Michał Pilipczuk, "Finding a maximum induced degenerate subgraph faster than 2^n" by Marcin Pilipczuk and Michał Pilipczuk, and "An exact algorithm for subset feedback vertex set on chordal graphs" by Petr Golovach, Pinar Heggernes, Dieter Kratsch and Reza Saei have been accepted at IPEC 2012
- 09.07 Michał Pilipczuk gave a talk on the paper "Minimizing Rosenthal potential in multicast games", co-authored by Fedor V. Fomin, Petr Golovach and Jesper Nederlof, at ICALP 2012
- 05.07 Petr Golovach gave a talk on the paper "Induced disjoint paths in AT-Free graphs", co-authored by Daniël Paulusma and Erik Jan van Leeuwen, at SWAT 2012
- 29.06 Petr Golovach gave a talk on the paper "How to eliminate a graph", co-authored by Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma and Michał Pilipczuk, at WG 2012
- 27.06 Michał Pilipczuk gave a talk and got the Best Student Paper Award at WG 2012 for the paper "On group feedback vertex set parameterized by the size of the cutset", co-authored by Marek Cygan and Marcin Pilipczuk
- 26.06 Petr Golovach gave a talk on the paper "Solutions for the stable roommates problem with payments", co-authored by Peter Biro, Matthijs Bomhoff, Walter Kern and Daniël Paulusma, at WG 2012
- 23.06 Papers "Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms" by Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra and Saket Saurabh, and "Designing FPT algorithms for cut problems using randomized contractions" by Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk and Michał Pilipczuk, have been accepted at FOCS 2012
- 22.06 Article of Pål Grønås Drange and Jan Arne Telle File:Groenas-telle.pdf (PDF) appeared in Bergens Tidende.
- 21.06 Arash Rafiey gave a talk "Bipartite Graphs and Approximation of Minimum Cost Homomorphisms" at SIAM Conference on Discrete Math.
- 21.06 Article of Pål Grønås Drange and Jan Arne Telle Er du venn med en robot? appeared in Morgenbladet
- 17.06 Papers "A polynomial kernel for Proper Interval Vertex Deletion" by Fedor V. Fomin, Saket Saurabh and Yngve Villanger, and "Induced disjoint paths in claw-free graphs" by Petr Golovach, Daniël Paulusma and Erik Jan van Leeuwen, "Approximation of Minimum Cost Homomorphisms" by Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, and Arash Rafiey have been accepted at ESA 2012
- 05.06 Papers "Sitting closer to friends than enemies, revisited" by Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk, "Coloring graphs characterized by a forbidden subgraph" by Petr Golovach, Daniël Paulusma and Bernard Ries, and "Obtaining planarity by contracting few edges" by Petr Golovach, Pim Van 'T Hof and Daniël Paulusma have been accepted at MFCS 2012
- 11-15.06 Fedor V. Fomin and Michał Pilipczuk participated in Dagstuhl seminar 12241 "Data Reduction and Problem Kernels". Michał gives a talk on recent results about hardness of Edge Clique Cover. Fedor gave a talk on "Mike Fellows in kernelization: From Lost Continent to the Land of Promise".
- 01-08.06 School on Rankwidth and Matroids by Sang-il Oum (KAIST, South Korea) and Dimitrios Thilikos (National and Kapodistrian University of Athens, Greece)
- 29.04 Papers "On group feedback vertex set parameterized by the size of the cutset" by Marek Cygan, Marcin Pilipczuk and Michał Pilipczuk, and "How to eliminate a graph" by Petr Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma and Michał Pilipczuk, have been accepted at WG 2012
- 17.04 Michał Pilipczuk gave a talk on the paper "Solving 2-Disjoint Connected Subgraphs problem faster than 2^n", co-authored by Marek Cygan, Marcin Pilipczuk and Jakub Onufry Wojtaszczyk, at LATIN 2012
- 17.04 Papers "Clique cover and graph separation: New incompressibility results" by Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström, "Fixed-parameter tractability of multicut in directed acyclic graphs" by Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström, and "Minimizing Rosenthal potential in multicast games" by Fedor V. Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk, have been accepted at ICALP 2012
- 01.04 Petr Golovach started as a researcher
- 12-18.03 School on Graph Isomorphism by Pascal Schweitzer (Institut Mittag-Leffler, Sweden)
- 02.03 Fedor Fomin gave a talk on the paper "Parameterized Complexity of Connected Even/Odd Subgraph Problems" at STACS 2012
- 25.01 Fedor Fomin gave an invited talk "Kernelization Algorithms" at Symposium »Logic and Algorithms: A Scientific Perspective«
- 01.01 Pål Grønås Drange arranged Turing Centenary: Turing2012 at the University of Bergen
- 01.01 Pål Grønås Drange started as a PhD student
2011
- 11-16.12 Fedor V. Fomin and Michał Pilipczuk participated in the Second Bertinoro Workshop on Algorithms and Graphs. Fedor gave a talk on subexponential algorithm for Minimum Fill-in, and Michał gave a talk on recent developments in minor-related problems in tournaments.
- 30.11 Paper "Parameterized Complexity of Connected Even/Odd Subgraph Problems" by Fedor V. Fomin and Petr Golovach has been accepted at STACS 2012
- 17.11 Papers "Solving the 2-Disjoint Connected Subgraphs problem faster than 2^n" by Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk, and "k-gap interval graphs" by Fedor Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle and Yngve Villanger, have been accepted at LATIN 2012
- 17.11 Fedor Fomin gave a talk on "Introduction to kernelization" at Colloquium Jacques Morgenstern
- 01.11 Arash Rafiey started as a researcher
- 05.09 Papers "Linear Kernels for (Connected) Dominating Set on H-minor-free graphs" by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos, "Bidimensionality and Geometric Graphs" by Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh, and "Subexponential Parameterized Algorithm for Minimum Fill-in" by Fedor V. Fomin and Yngve Villanger, have been accepted at SODA 2012
- 15.09 Michał Pilipczuk started as a PhD student
- 03.09 Fedor Fomin gave a keynote talk on "Protrusions in graphs and their applications" at WORKER 2011. Slides of the talk are here.
- 16.07 Paper "Parameterized Complexity of Firefighting Revisited" by Marek Cygan, Fedor V. Fomin and Erik Jan van Leeuwen has been accepted at IPEC 2011
- 19-20.05 Treewidth Workshop
- 01.04 Start of the project