Algorithms
Group publications
Unfortunately we are not able to keep this list updated. Please check the home page of every group member for recent publications.
Main content
Other useful resources for searching for publications of our group members:
DBLP computer science bibliography
CRISTIN Current Research Information System In Norway
2018
Publications in 2018
- Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi:Parameterized algorithms for stable matching with ties and incomplete lists. Theor. Comput. Sci. 723: 1-10 (2018)
- Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi:Erdös-Pósa Property of Obstructions to Interval Graphs. STACS 2018: 7:1-7:15
- Akanksha Agrawal, Saket Saurabh, Roohani Sharma, Meirav Zehavi: Kernels for deletion to classes of acyclic digraphs. J. Comput. Syst. Sci. 92: 9-21 (2018)
- Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: A Polynomial Sized Kernel for Tracking Paths Problem. LATIN 2018: 94-107
- Aritra Banik, Fahad Panolan, Venkatesh Raman, Vibha Sahlot: Fréchet Distance Between a Line and Avatar Point Set. Algorithmica 80(9): 2616-2636 (2018)
- Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi: Parameterized Algorithms for Survivable Network Design with Uniform Demands. SODA 2018: 2838-2850
- Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh:On the kernelization complexity of string problems. Theor. Comput. Sci. 730: 21-31 (2018)
- Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma: Independent feedback vertex sets for graphs of bounded diameter. Inf. Process. Lett. 131: 26-32 (2018)
- Mateus de Oliveira Oliveira: Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function. Theory Comput. Syst. 62(1): 136-161 (2018)
- Mateus de Oliveira Oliveira: A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth. SODA 2018: 136-145
- Eduard Eiben, Robert Ganian, Stefan Szeider: Solving Problems on Graphs of High Rank-Width. Algorithmica 80(2): 742-771 (2018)
- Eduard Eiben, Jonathan Gemmell, Iyad A. Kanj, Andrew Youngdahl: Improved Results for Minimum Constraint Removal. AAAI 2018
- Eduard Eiben, Robert Ganian, Sebastian Ordyniak: Small Resolution Proofs for QBF using Dependency Treewidth. STACS 2018: 28:1-28:15
- Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz: Lossy Kernels for Connected Dominating Set on Sparse Graphs. STACS 2018: 29:1-29:15
- Carl Feghali, Matthew Johnson, Daniel Thomas: Erdős-Ko-Rado theorems for a family of trees. Discrete Applied Mathematics 236: 464-471 (2018)
- Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca: Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques. Algorithmica 80(4): 1146-1169 (2018)
- Fedor V. Fomin, Saket Saurabh: Preface to Special Issue Dedicated to the 60th Birthday of Gregory Gutin. Algorithmica 80(9): 2513-2515 (2018)
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos: Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors. ACM Trans. Algorithms 14(1): 6:1-6:31 (2018)
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh: Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes. J. ACM 65(2): 10:1-10:44 (2018)
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos: Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors. ACM Trans. Algorithms 14(1): 6:1-6:31 (2018)
- Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther, Yngve Villanger: Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica 80(2): 714-741 (2018)
- Petr A. Golovach, Pinar Heggernes, Dieter Kratsch: Enumeration and maximum number of minimal connected vertex covers in graphs. Eur. J. Comb. 68: 132-147 (2018)
- Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi: Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. SODA 2018: 262-273
- Lars Jaffke, O-joung Kwon, Jan Arne Telle: A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. STACS 2018: 42:1-42:14
- Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra: Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized. CSR 2018: 194-206
- Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen: Independence and Efficient Domination on P6-free Graphs. ACM Trans. Algorithms 14(1): 3:1-3:30 (2018)
- Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh: Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. ACM Trans. Algorithms 14(1): 7:1-7:37 (2018)
- Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi: Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. ITCS 2018: 32:1-32:13
- Daniel Lokshtanov, Amer E. Mouawad: The complexity of independent set reconfiguration on bipartite graphs. SODA 2018: 185-195
- Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi, Pavel Pudlák: Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth. SODA 2018: 247-261
- Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi: Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. SODA 2018: 331-342
- Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh: When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices. SODA 2018: 1916-1933
- Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi: Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. SODA 2018: 2785-2800
- Fedor V. Fomin, Saket Saurabh: Preface to Special Issue Dedicated to the 60th Birthday of Gregory Gutin. Algorithmica 80(9): 2513-2515 (2018)
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh: Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes. J. ACM 65(2): 10:1-10:44 (2018)
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos: Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors. ACM Trans. Algorithms 14(1): 6:1-6:31 (2018)
- Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh: Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. ACM Trans. Algorithms 14(1): 7:1-7:37 (2018)
- Ashutosh Rai, Saket Saurabh: Bivariate complexity analysis of Almost Forest Deletion. Theor. Comput. Sci. 708: 18-33 (2018) Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi: Max-Cut Above Spanning Tree is Fixed-Parameter Tractable. CSR 2018: 244-256
- Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi: Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. ITCS 2018: 32:1-32:13
- Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: A Polynomial Sized Kernel for Tracking Paths Problem. LATIN 2018: 94-107
- R. Krithika, Abhishek Sahu, Saket Saurabh, Meirav Zehavi: The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue. LATIN 2018: 712-726
- Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi: Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. SODA 2018: 262-273
- Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi: Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. SODA 2018: 331-342
- Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh: When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices. SODA 2018: 1916-1933
- Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi: Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. SODA 2018: 2785-2800
- Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi: Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. ITCS 2018: 32:1-32:13
- Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi: Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. SODA 2018: 2785-2800
- Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi: Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. ITCS 2018: 32:1-32:13
2014
Publications in 2014
- Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma: Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica 69(3): 501-521 (2014).
- Rémy Belmonte, Pinar Heggernes, Pim van 't Hof, Arash Rafiey, Reza Saei: Ramsey numbers for graph classes. Discrete Applied Mathematics 173: 16-27 (2014)
- Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Christophe Paul: Contracting chordal graphs and bipartite graphs to paths and trees. Discrete Applied Mathematics 164(2): 444-449 (2014)
- Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul: Contracting Graphs to Paths and Trees. Algorithmica 68(1): 109-132 (2014).
- Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger: Enumerating Minimal Subset Feedback Vertex Sets. Algorithmica 69(1): 216-231 (2014).
- André Berger, Alexander Grigoriev, Pinar Heggernes, Ruben van der Zwaan: Scheduling unit-length jobs with precedence constraints of small height. Oper. Res. Lett. 42(2): 166-172 (2014).
- Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen, Reza Saei: Finding Disjoint Paths in Split Graphs. SOFSEM 2014: 315-326.
- Pinar Heggernes, Jan Kratochvil, Sang-il Oum (guest editors): Fifth Workshop on Graph Classes, Optimization, and Width Parameters - Daejeon, South Korea - October 2011. Discrete Applied Mathematics 168 (2014).
- Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. SODA 2014.
- Bart Jansen, Daniel Lokshtanov and Saket Saurabh: A Near-Optimal Planarization Algorithm. SODA 2014.
- Daniel Lokshtanov, Martin Vatshelle and Yngve Villanger: Independent Set in P5-Free Graphs in Polynomial Time. SODA 2014.
- Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger: Exploring Subexponential Parameterized Complexity of Completion Problems. STACS 2014.
- Dániel Marx, Michał Pilipczuk: Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). STACS 2014.
- Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh: Minimum Bisection is fixed-parameter tractable. STOC 2014.
- Andre Berger, Alexander Grigoriev, Pinar Heggernes, and Ruben van der Zwaan: Scheduling unit-length jobs with precedence constraints of small height. Operation Research Letters 42: 166-172 (2014).
- Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Yngve Villanger: Maximal induced matchings in triangle-free graphs. WG 2014.
- Petr Golovach, Pinar Heggernes, Pim van 't Hof, and Christophe Paul: Hadwiger Number of Graphs with Small Chordality. WG 2014.
- Vinicius dos Santos, Petr Golovach, Pinar Heggernes, Nathan Lindzey, Ross McConnell, and Jeremy Spinrad: Recognizing Threshold Tolerance Graphs in O(n2) Time. WG 2014.
- Sigve Hortemo Sæther and Jan Arne Telle: Between treewidth and clique-width. WG 2014.
- Sigve Hortemo Sæther, Jan Arne Telle, and Martin Vatshelle: Solving MaxSAT and #SAT on structured CNF formulas. SAT 2014.
- Sang-il Oum, Sigve Hortemo Sæther, and Martin Vatshelle: Faster algorithms for vertex partitioning problems parameterized by clique-width. Theoretical Computer Science 535: 16-24.
2013
Publications in 2013
- Steven Chaplick, Jiří Fiala, Pim van 't Hof, Daniël Paulusma, Marek Tesař: Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree, FCT 2013.
- Rémy Belmonte, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma, and Dimitrios M. Thilikos: Characterizing graphs of small carving-width, Discrete Applied Mathematics 161(13-14): 1888-1893 (2013)
- Pinar Heggernes, Pim van 't Hof, Bart Jansen, Stefan Kratsch, and Yngve Villanger: Parameterized complexity of vertex deletion into perfect graph classes, Theoretical Computer Science 511: 172-180 (2013)
- Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul: Obtaining a bipartite graph by contracting few edges, SIAM Journal on Discrete Mathematics 27(4): 2143-2156 (2013)
- Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk: Known algorithms for Edge Clique Cover are probably optimal, SODA 2013.
- Fedor V. Fomin and Michał Pilipczuk: Jungles, bundles, and fixed parameter tractability, SODA 2013.
- Tinaz Ekim, Pinar Heggernes and Daniel Meister: Polar permutation graphs are polynomial-time recognisable, European Journal of Combinatorics, 34: 576-592 (2013).
- Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Yngve Villanger, Tight bounds for Parameterized Complexity of Cluster Editing, STACS 2013.
- Fedor Fomin and Yngve Villanger, Searching for better fill-in, STACS 2013.
- Henning Fernau, Pinar Heggernes, and Yngve Villanger: A multivariate analysis of some DFA problems, LATA 2013.
- Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Arash Rafiey: Cliques and Clubs, CIAC 2013.
- Petr Golovach, Pinar Heggernes, Pim van 't Hof, and Daniel Paulusma: Choosability on H-free graphs, Information Processing Letters 113:107-110 (2013).
- Endre Boros, Pinar Heggernes, Pim van 't Hof, and Martin Milanic: Vector connectivity in graphs, TAMC 2013.
- Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, ICALP 2013.
- Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca and Yngve Villanger: Treewidth and pathwidth parameterized by vertex cover, WADS 2013.
- Jan Arne Telle and Yngve Villanger: Connecting terminals and 2-disjoint connected subgraphs, WG 2013
- Hajo Broersma, Jiri Fiala, Petr Golovach, Tomas Kaiser, Daniel Paulusma and Andrzej Proskurowski: Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs, WG 2013.
- Archontia Giannopoulou, Marcin Kamiński and Dimitrios Thilikos: Excluding graphs as immersions in surface embedded graphs, WG 2013.
- Konrad Dabrowski, Petr Golovach and Daniel Paulusma: Colouring of graphs with Ramsey-type forbidden subgraphs, WG 2013.
- Manfred Cochefert, Jean-François Couturier, Petr Golovach, Dieter Kratsch and Daniel Paulusma: Sparse square roots, WG 2013.
- Neeldhara Misra, Fahad Panolan, Ashutosh Rai, Venkatesh Raman and Saket Saurabh: Parameterized algorithms for max colorable induced subgraph problem on perfect graphs, WG 2013.
- Pinar Heggernes, Pim van 't Hof and Martin Milanic: Induced Subtrees in Interval Graphs, IWOCA 2013.
- Pim van 't Hof and Yngve Villanger: Proper interval vertex deletion, Algorithmica 65(4):845-867 (2013).
- Rémy Belmonte, Pim van 't Hof, Marcin Kamiński and Daniël Paulusma: The price of connectivity for Feedback Vertex Set, Eurocomb 2013.
- Hajo Broersma, Fedor V. Fomin, Pim van 't Hof, and Daniël Paulusma: Exact algorithms for finding longest cycles in claw-free graphs, Algorithmica 65:129-145 (2013).
- Petr A. Golovach, Pim van 't Hof, and Daniël Paulusma: Obtaining planarity by contracting few edges, Theoretical Computer Science 476:38-46 (2013).
- Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, and Dieter Kratsch: Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Theoretical Computer Science 487:82-94 (2013).
- Hans Bodlaender, Pål Drange, Markus Dregi, Fedor Fomin, Daniel Lokshtanov and Michał Pulipczuk: An O(c^k) n 5-Approximation Algorithm for Treewidth, FOCS 2013.
- Marek Cygan, Daniel Marx, Marcin Pilipczuk and Michał Pilipczuk: The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable, FOCS 2013.
- Fedor Fomin, Daniel Lokshtanov, Rajesh Chitnis, Pranabendu Misra, Ramanujan M. S. and Saket Saurabh. Faster Exact Algorithms for Some Terminal Set Problems, IPEC 2013.
- Ramanujan M. S., Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh and Geevarghese Philip. Hardness of r-Dominating Set on graphs of diameter (r+1), IPEC 2013.
- Fedor Fomin, Archontia Giannopoulou and Michał Pilipczuk. Computing Tree-depth Faster Than 2^n, IPEC 2013.
- Hans Bodlaender, Paul Bonsma and Daniel Lokshtanov. The fine details of fast dynamic programming over tree decompositions, IPEC 2013.
- Olawale Hassan, Iyad Kanj, Daniel Lokshtanov and Ljubomir Perkovic. On the Ordered List Subgraph Embedding Problems, IPEC 2013.
- Daniel Lokshtanov, Neeldhara Misra and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges, IPEC 2013.
- Yuri Rabinovich, Jan Arne Telle and Martin Vatshelle. Upper bounds on boolean-width with applications to exact algorithms, IPEC 2013.
- Rémy Belmonte, Petr Golovach, Pim van 't Hof and Daniel Paulusma. Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints, IPEC 2013.
- Fedor Fomin and Michał Pilipczuk. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph, ESA 2013.
- Fedor Fomin and Petr Golovach. Long Circuits and Large Euler Subgraphs, ESA 2013.
- Ramanujan M. S., Saket Saurabh, Daniel Lokshtanov, Ondrej Suchy and Mark Jones. Parameterized Complexity of Directed Steiner Tree on Sparse Graph, ESA 2013.
- Ivan Bliznets, Fedor Fomin, Michał Pilipczuk and Yngve Villanger. Largest chordal and interval subgraphs faster than 2^n, ESA 2013.
2012
Publications in 2012
- Fedor V. Fomin, Dániel Marx: FPT Suspects and Tough Customers: Open Problems of Downey and Fellows. The Multivariate Algorithmic Revolution and Beyond 2012: 457-468
- Fedor V. Fomin, Saket Saurabh, Yngve Villanger: A Polynomial Kernel for Proper Interval Vertex Deletion. ESA 2012: 467-478
- Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric, Nicolas Nisse: To Satisfy Impatient Web Surfers Is Hard. FUN 2012: 166-176
- Fedor V. Fomin, Bart M. P. Jansen, Michal Pilipczuk: Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help? IPEC 2012: 97-108
- Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger: k-Gap Interval Graphs. LATIN 2012: 350-361
- Fedor V. Fomin, Petr A. Golovach: Parameterized Complexity of Connected Even/Odd Subgraph Problems. STACS 2012: 432-440
- Fedor V. Fomin, Fabrizio Grandoni, Daniel Lokshtanov, Saket Saurabh: Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica 63(3): 692-706 (2012)
- Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos: Fast Minor Testing in Planar Graphs. Algorithmica 64(1): 69-84 (2012)
- Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, Erik Jan van Leeuwen: Parameterized Complexity of the Spanning Tree Congestion Problem. Algorithmica 64(1): 85-111 (2012)
- Fedor V. Fomin, Yngve Villanger: Treewidth computation and extremal combinatorics. Combinatorica 32(3): 289-308 (2012)
- Lali Barrière, Paola Flocchini, Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse, Nicola Santoro, Dimitrios M. Thilikos: Connected graph searching. Inf. Comput. 219: 1-16 (2012)
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, B. V. Raghavendra Rao: Faster algorithms for finding and counting subgraphs. J. Comput. Syst. Sci. 78(3): 698-706 (2012)
- Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Yngve Villanger: Local search: Is brute-force avoidable? J. Comput. Syst. Sci. 78(3): 707-719 (2012)
- Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos: Catalan structures and dynamic programming in H-minor-free graphs. J. Comput. Syst. Sci. 78(5): 1606-1622 (2012)
- Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos: A Note on Exact Algorithms for Vertex Ordering Problems on Graphs. Theory Comput. Syst. 50(3): 420-432 (2012)
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov: Cops and Robber Game Without Recharging. Theory Comput. Syst. 50(4): 611-620 (2012)
- Fedor V. Fomin, Petr A. Golovach, Pawel Pralat: Cops and Robber with Constraints. SIAM J. Discrete Math. 26(2): 571-590 (2012)
- Omid Amini, Fedor V. Fomin, Saket Saurabh: Counting Subgraphs via Homomorphisms. SIAM J. Discrete Math. 26(2): 695-717 (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)
- Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos: On exact algorithms for treewidth. ACM Transactions on Algorithms 9(1): 12 (2012)
- Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, Dimitrios M. Thilikos: Foreword: Special Issue on Theory and Applications of Graph Searching Problems. Theor. Comput. Sci. 463: 1 (2012)
- Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, and Dieter Kratsch: Minimal dominating sets in graph classes: combinatorial bounds and enumeration, SOFSEM 2012.
- Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof and Pekka Parviainen: Fast zeta transforms for point lattices, SODA 2012.
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos: Linear Kernels for (Connected) Dominating Set on H-minor-free graphs, SODA 2012.
- Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh: Bidimensionality and Geometric Graphs, SODA 2012.
- Fedor V. Fomin and Yngve Villanger: Subexponential Parameterized Algorithm for Minimum Fill-in, SODA 2012.
- Tinaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof, and Daniel Meister: Computing minimum geodetic sets in proper interval graphs, LATIN 2012.
- Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Wojtaszczyk: Solving the 2-Disjoint Connected Subgraphs problem faster than 2^n, LATIN 2012.
- Fedor Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle and Yngve Villanger: k-gap interval graphs, LATIN 2012.
- Pinar Heggernes and Sigve H. Sæther: Broadcast Domination on block graphs in linear time, CSR 2012.
- Fedor V. Fomin, Pinar Heggernes, and Erik Jan van Leeuwen: Making life easier for firefighters, FUN 2012.
- Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric and Nicolas Nisse: To Satisfy Impatient Web surfers is Hard, FUN 2012.
- Pinar Heggernes, Jan Kratochvil, and Andrzej Proskurowski: Fourth Workshop on Graph Classes, Optimization, and Width Parameters - Bergen, Norway - October 2009, Discrete Applied Mathematics 160-6: 683-921 (2012).
- Petr Golovach, Pinar Heggernes, and Rodica Mihai: Edge search number of cographs, Discrete Applied Mathematics 160: 734-743 (2012).
- Pinar Heggernes, Daniel Meister, and Charis Papadopoulos: Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs, Discrete Applied Mathematics 160: 888-901 (2012).
- Pim van 't Hof, Marcin Kamiński, Daniël Paulusma, Stefan Szeider and Dimitrios M. Thilikos: On graph contractions and induced minors, Discrete Applied Mathematics 160: 799-809 (2012).
- Rémy Belmonte, Pinar Heggernes, and Pim van 't Hof: Edge contractions in subclasses of chordal graphs, Discrete Applied Mathematics 160: 999-1010 (2012).
- Remy Belmonte, Pinar Heggernes, Pim van 't Hof, and Reza Saei: Ramsey numbers for line graphs and perfect graphs, COCOON 2012.
- Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, and Yngve Villanger: Maximum number of minimal feedback vertex sets in chordal graphs and cographs, COCOON 2012.
- Pim van 't Hof, Marcin Kamiński and Daniël Paulusma: Finding induced paths of given parity on claw-free graphs, Algorithmica 62: 537-563 (2012).
- Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström: Clique cover and graph separation: New incompressibility results, ICALP 2012.
- Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström: Fixed-parameter tractability of multicut in directed acyclic graphs, ICALP 2012.
- Fedor Fomin, Petr Golovach, Jesper Nederlof, and Michał Pilipczuk: Minimizing Rosenthal potential in multicast games, ICALP 2012.
- Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk: On group feedback vertex set parameterized by the size of the cutset, WG 2012.
- Petr Golovach, Pinar Heggernes, Pim van't Hof, Fredrik Manne, Daniël Paulusma, and Michał Pilipczuk:How to eliminate a graph, WG 2012.
- Pinar Heggernes, Pim van 't Hof, Daniel Marx, Neeldhara Misra, and Yngve Villanger: On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties, WG 2012.
- Rémy Belmonte, Pim van 't Hof, Marcin Kaminski, Daniel Paulusma, and Dimitrios Thilikos: Characterizing Graphs of Small Carving-Width, COCOA 2012.
- Pinar Heggernes, Pim van 't Hof, and Daniel Paulusma: Computing role assignments of proper interval graphs in polynomial time, Journal of Discrete Algorithms 14: 173-188 (2012).
- Jan Arne Telle and Yngve Villanger: Solving domination problems on larger graph classes by linear-time FPT algorithm, ESA 2012.
- Fedor Fomin, Saket Saurabh, and Yngve Villanger: A Polynomial kernel for Proper Interval Vertex Deletion, ESA 2012.
- Petr Golovach, Daniel Paulusma and Erik Jan van Leeuwen. Induced Disjoint Paths in Claw-Free Graphs, ESA 2012.
- Pavol Hell, Monaldo Mastrolilli, Mayssam Nevisi and Arash Rafiey. Approximation of Minimum Cost Homomorphisms, ESA 2012.
- Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh: Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms, FOCS 2012.
- Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk and Michał Pilipczuk: Designing FPT algorithms for cut problems using randomized contractions, FOCS 2012.
- Marcin Pilipczuk and Michal Pilipczuk: Finding a maximum induced degenerate subgraph faster than 2^n, IPEC 2012.
- Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Reza Saei: An exact algorithm for Subset Feedback Vertex Set on chordal graphs, IPEC 2012.
- Fedor V. Fomin, Bart Jansen, and Michal Pilipczuk: Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?, IPEC 2012.
- Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Jesper Nederlof: Computing the cutwidth of bipartite permutation graphs in linear time, SIAM Journal on Discrete Mathematics 26: 1008-1021 (2012).
- Rémy Belmonte, Pim van 't Hof and Marcin Kaminski. Induced Immersions, ISAAC 2012.
- Petr Golovach, Dieter Kratsch and Daniel Paulusma. Detecting Induced Minors in AT-free Graphs, ISAAC 2012.
- Petr Golovach, Daniel Paulusma and Jian Song. Closing Complexity Gaps for Coloring Problems on H-Free Graphs, ISAAC 2012.
2011
Publications in 2011
- Fedor V. Fomin, Petr A. Golovach, Alexander Hall, Matús Mihalák, Elias Vicari, Peter Widmayer: How to Guard a Graph? Algorithmica 61(4): 839-856 (2011)
- Michael R. Fellows, Fedor V. Fomin, Gregory Gutin: Special Issue on Parameterized Complexity of Discrete Optimization. Discrete Optimization 8(1): 1 (2011)
- Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412(50): 7018-7028 (2011)
- Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos: Approximating Width Parameters of Hypergraphs with Excluded Minors. SIAM J. Discrete Math. 25(3): 1331-1348 (2011)
- Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, Dimitrios M. Thilikos: Special Issue on "Theory and Applications of Graph Searching Problems". Theor. Comput. Sci. 412(24): 2699 (2011)
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov: Guard games on graphs: Keep the intruder out! Theor. Comput. Sci. 412(46): 6484-6497 (2011)
- Johannes Langguth, Md. Mostofa Ali Patwary, Fredrik Manne: Parallel algorithms for bipartite matching problems on distributed memory computers. Parallel Computing 37(12): 820-845 (2011)
- Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger: Faster Parameterized Algorithms for Minimum Fill-in. Algorithmica 61(4): 817-838 (2011)
- Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, Charis Papadopoulos: Cutwidth of Split Graphs and Threshold Graphs. SIAM J. Discrete Math. 25(3): 1418-1437 (2011)
- Pinar Heggernes, Daniel Meister, Charis Papadopoulos: Graphs of linear clique-width at most 3. Theor. Comput. Sci. 412(39): 5466-5486 (2011)
- Petr Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh: Bandwidth on AT-free graphs. Theor. Comput. Sci. 412: 7001-7008 (2011).
- Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle: Boolean-width of graphs. Theor. Compu. Sci. 412(39): 5187-5204 (2011)
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh: An exact algorithm for minimum distortion embedding. Theor. Comput. Sci. 412(29): 3530-3536 (2011)
- Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, Federico Mancini, Jan Arne Telle: On the complexity of reconstructing H-free graphs from their Star Systems. Journal of Graph Theory 68(2): 113-124 (2011)
- Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos: Strengthening Erdös-Pósa property for minor-closed graph classes. Journal of Graph Theory 66(3): 235-240 (2011)
- Omid Amini, Fedor V. Fomin, Saket Saurabh: Implicit branching and parameterized partial cover problems. J. Comput. Syst. Sci. 77(6): 1159-1171 (2011)
- Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach: Spanners in sparse graphs. J. Comput. Syst. Sci. 77(6): 1108-1119 (2011)
- Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, Stéphan Thomassé: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. 77(6): 1071-1078 (2011)
- Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos: Contraction obstructions for treewidth. J. Comb. Theory, Ser. B 101(5): 302-314 (2011)
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: Subexponential algorithms for partial cover problems. Inf. Process. Lett. 111(16): 814-818 (2011)
- Pinar Heggernes, Daniel Meister, and Andrzej Proskurowski: Computing minimum distortion embeddings into a path of bipartite permutation graphs and threshold graphs. Theoretical Computer Science 411: 1275-1297 (2011).
- Rémy Belmonte, Pinar Heggernes, and Pim van 't Hof: Edge contractions in subclasses of chordal graphs. TAMC 2011.
- Pinar Heggernes, Daniel Meister, and Udi Rotics: Computing the clique-width of large path powers in linear time via a new characterisation of clique-width. CSR 2011.
- Pinar Heggernes, Pim van 't Hof, Benjamin Leveque, and Christophe Paul: Contracting chordal graphs and bipartite graphs to paths and trees. LAGOS 2011.
- Daniel Lokshtanov, Daniel Marx, and Saket Saurabh: Known algorithms on graphs of bounded treewidth are probably optimal. SODA 2011.
- Daniel Lokshtanov, Daniel Marx, and Saket Saurabh:Slilghtly superexponential parameterized algorithms. SODA 2011.
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh: Bidimensionality and EPTAS. SODA 2011.
- Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach: Approximation of minimum weight spanners for sparse graphs. Theor. Comput. Sci. 412(8-10): 846-852 (2011)
- Fedor V. Fomin, Petr A. Golovach, Erik Jan van Leeuwen: Spanners of bounded degree graphs. Inf. Process. Lett. 111(3): 142-144 (2011)
- Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2): 143-153 (2011)
- Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica 61(2): 252-273 (2011)
- Binh-Minh Bui-Xuan, Pinar Heggernes, Ross McConnell, Daniel Meister, and Andrzej Proskurowski: A generic approach to decomposition algorithms, with an application to digraph decomposition. COCOON 2011.
- Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh: Hitting forbidden minors: Approximation and Kernelization. STACS 2011: 189-200
- Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger: Enumerating minimal subset feedback vertex sets. WADS 2011.
- Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Exact algorithm for the maximum induced planar subgraph problem, ESA 2011.
- Pinar Heggernes, Pim van 't Hof, Bart Jansen, Stefan Kratsch, and Yngve Villanger, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, FCT 2011.
- Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul: Obtaining a Bipartite Graph by Contracting Few Edges, FSTTCS 2011.
- Pinar Heggernes, Pim van 't Hof, Benjamin Leveque, Daniel Lokshtanov, and Christophe Paul: Contracting Graphs to Paths and Trees, IPEC 2011.
- Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski, and Daniel Paulusma: Finding contractions and induced minors in chordal graphs via disjoint paths, ISAAC 2011.
- Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and R. Sritharan: Strongly chordal and chordal bipartite graphs are sandwich monotone, Journal of Combinatorial Optimization 22 (2011) : 438-456.
- Rémy Belmonte and Martin Vatshelle: Graph Classes with Structured Neighborhood and Algorithmic Applications, WG 2011.
- Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time, FOCS 2011.
- Fedor V. Fomin, Geevarghese Philip, and Yngve Villanger: Minimum Fill-In of Sparse graphs: Kernelization and Approximation, FSTTCS 2011.
- Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen: Parameterized Complexity of Firefighting Revisited, IPEC 2011.
- Eivind Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle, Finding good decompositions for dynamic programming on dense graphs, IPEC 2011
- Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger: Domination when the stars are out, ICALP 2011.
- T. M. Müller, Erik Jan van Leeuwen, Jan van Leeuwen: Integer Representations of Convex Polygon Intersection Graphs. SoCG, 2011.
- Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil: A self-stabilizing 2/3-approximation algorithm for the maximum matching problem. Theor. Comput. Sci. 412(40): 5515-5526 (2011).
- M. Cygan, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk and S.Saurabh: On Cutwidth Parameterized by Vertex Cover. Proceedings of the International Symposium on Parameterized and Exact Computation, IPEC 2011.
- M.Cygan, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk and S.Saurabh: On The Hardness of Losing Width. Proceedings of the International Symposium on Parameterized and Exact Computation, IPEC 2011.
- Daniel Lokshtanov, Matthias Mnich and Saket Saurabh: Planar k-Path in Subexponential Time and Polynomial Space. To appear in the proceedings of Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011.
- I.Adler, S.G.Kolliopoulos, P.K.Krause, D.Lokshtanov, S.Saurabh and D.Thilikos: Tight Bounds for Linkages in Planar Graphs. Proceedings of the International Colloquium on Automata, Languages and Programming, ICALP 2011.
- Daniel Lokshtanov and Dániel Marx: Clustering with Local Restrictions. Proceedings of the International Colloquium on Automata, Languages and Programming, ICALP 2011.
- Paul Bonsma and Daniel Lokshtanov: Feedback Vertex Set in Mixed Graps. Proceedings of the Algorithms and Data Structures Symposium, WADS 2011.
- O. Owe, M. Steffen, J. A. Telle (editors): Proceedings Fundamentals of Computation Theory, Oslo, Norway, August 2011, Lecture Notes in Computer Science 6914 (2011) , Springer.
- Md. Mostofa Ali Patwary, Assefaw H. Gebremedhin, and Alex Pothen: New Multithreaded Ordering and Coloring Algorithms for Multicore Architectures, Euro-Par 2011.
2010
Publications in 2010
- Frederic Dorn, Hannes Moser, Rolf Niedermeier and Mathias Weller: Efficient Algorithms for Eulerian Extension. WG 2010: 100 - 111
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh: Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941-1956 (2010)
- Fedor V. Fomin, Pinar Heggenes, and Rodica Mihai: Mixed search number and linear-width of interval and split graphs. Networks 56: 207-214 (2010).
- Pim van 't Hof, Gerhard Post, and Dirk Briskorn: Constructing fair round robin tournaments with a minimum number of breaks. Operation Research Letters 38: 592-596 (2010).
- Pim van 't Hof, Daniel Paulusma, and Johan M. M. van Rooij: Computing role assignments of chordal graphs. Theoretical Computer Science 411: 40-42 (2010).
- Ariful Azad, Johannes Langguth, Youhan Fang, Alan Qi, Alex Pothen: Identifying Rare Cell Populations in Comparative Flow Cytometry. WABI 2010: 162-175
- D. Bozdag, U. Catalyurek, A. Gebremedhin, F. Manne, E. Boman and F. Ozguner, Distributed-memory Parallel Algorithms for Distance-2 Coloring and Related Problems in Derivative Computation, SIAM Journal on Scientific Computing Vol 32, Issue 4, pp 2418--2446, 2010.
- M. Patwary, R. Bisseling, and F. Manne, Parallel greedy graph matching using an edge partitioning approach. HLPP'10. ACM, pp 45-54.
- Jean R. S. Blair, Fredrik Manne, Rodica Mihai: Efficient Self-stabilizing Graph Searching in Tree Networks. SSS 2010: 111-125
- Johannes Langguth, Fredrik Manne, Peter Sanders: Heuristic initialization for bipartite matching problems. ACM Journal of Experimental Algorithmics 15: (2010)
- Md. Mostofa Ali Patwary, Jean R. S. Blair, Fredrik Manne: Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure. SEA 2010: 411-423
- F. Dorn, E. Penninkx, H. L. Bodlaender, and F. V. Fomin. Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions. Algorithmica.58(3): pages 790-810, 2010
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments. AAAI 2010
- Daniel Meister: Treewidth and minimum fill-in on permutation graphs in linear time. Theor. Comput. Sci. 411(40-42): 3685-3700 (2010)
- I.Adler, B-M Bui-Xuan, Y.Rabinovich, G.Renault, J.A.Telle and M.Vatshelle. On the boolean-width of a graph: structure and applications. Proceedings WG 2010, LNCS
- Henning Fernau, Fedor V. Fomin, Geevarghese Philip, Saket Saurabh: The Curse of Connectivity: t-Total Vertex (Edge) Cover. COCOON 2010: 34-43
- Fedor V. Fomin: Kernelization. CSR 2010: 107-108
- Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos: Fast Minor Testing in Planar Graphs. ESA (1) 2010: 97-109
- Fedor V. Fomin, Daniel Lokshtanov, Fabrizio Grandoni, Saket Saurabh: Sharp Separation and Applications to Exact and Parameterized Algorithms. LATIN 2010: 72-83
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh: Algorithmic Lower Bounds for Problems Parameterized with Clique-Width. SODA 2010: 493-502
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos: Bidimensionality and Kernels. SODA 2010: 503-510
- Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. STACS 2010: 251-262
- Fedor V. Fomin, Yngve Villanger: Finding Induced Subgraphs via Minimal Triangulations. STACS 2010: 383-394
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov: Cops and Robber Game without Recharging. SWAT 2010: 273-284
- Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos: Faster Parameterized Algorithms for Minor Containment. SWAT 2010: 322-333
- Fedor V. Fomin, Sang-il Oum, Dimitrios M. Thilikos: Rank-width and tree-width of H-minor-free graphs. Eur. J. Comb. 31(7): 1617-1628 (2010)
- Nathann Cohen, Fedor V. Fomin, Gregory Gutin, Eun Jung Kim, Saket Saurabh, Anders Yeo: Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J. Comput. Syst. Sci. 76(7): 650-662 (2010)
- Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh: Iterative compression and exact algorithms. Theor. Comput. Sci. 411(7-9): 1045-1053 (2010)
- Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Pursuing a fast robber on a graph. Theor. Comput. Sci. 411(7-9): 1167-1181 (2010)
- Frederic Dorn: Planar Subgraph Isomorphism Revisited. STACS 2010: 263-274
- Frederic Dorn: Dynamic programming and planarity: Improved tree-decomposition based algorithms. Discrete Applied Mathematics 158(7): 800-808 (2010)
- Thomas Erlebach, Erik Jan van Leeuwen: PTAS for Weighted Set Cover on Unit Squares. APPROX-RANDOM 2010: 166-177
- Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, Martin Vatshelle: Faster Algorithms on Branch and Clique Decompositions. MFCS 2010: 174-185
- Hans L. Bodlaender, Mike Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and Frances Rosamond. Clustering with partial information. Theoretical Computer Science 411: 1202-1211 (2010)
- Pinar Heggernes and Daniel Meister. Hardness and approximation of minimum distortion embeddings. Information processing letters 110: 312-316 (2010)
- Pinar Heggernes, Daniel Meister and Yngve Villanger. Induced subgraph isomorphism on interval and proper interval graphs. ISAAC 2010
- Pinar Heggernes, Pim van 't Hof and Daniel Paulusma. Computing role assignments of proper interval graphs in polynomial time. IWOCA 2010
- Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Jesper Nederlof. Computing the cutwidth of bipartite permutation graphs in linear time. WG 2010
- Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul and Jan Arne Telle. Generalized graph clustering: recognizing (p,q)-cluster graphs. WG 2010
- Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh. Fixed parameter algorithms for cochromatic number and disjoint rectangle stabbing. SWAT 2010: 334-345
- Pinar Heggernes, Daniel Meister, and Udi Rotics. Explotining linear structure to cope with the hardness of clique-width. TAMC 2010: 284-295
- Pinar Heggernes, Federico Mancini, Jesper Nederlof, Yngve Villanger. A parameterized algorithm for chordal sandwich. CIAC 2010: 120-130
- Pinar Heggernes, Jan Kratochvil and Andrzej Proskurowski. Guest editors' foreword. Discrete Applied Mathematics 158: 729-730 (2010)
- Daniel Lokshtanov and Jesper Nederlof. Saving space by algebraization. STOC 2010: 321-330
- Jesper Nederlof and Johan M M van Rooij. Inclusion/exlusion branching for partial dominating set and set splitting. IPEC 2010
- G. Philip, Venkatesh Raman and Yngve Villanger. A quadratic kernel for pathwidth one vertex deletion. WG 2010
- Mathieu Liedloff, Ioan Todinca and Yngve Villanger. Solving capacitated dominating set by using covering by subsets and maximum matching. WG 2010
- Yngve Villanger. Proper interval vertex deletion. IPEC 2010
- Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh. Imbalance is fixed parameter tractable. COCOON 2010: 199-208
- Daniel Lokshtanov. Algorithmic lower bounds for problems on decomposable graphs. MFCS 2010: 37
- Daniel Lokshtanov, Federico Mancini and Charis Papadopoulos. Characterizing and computing minimal cograph completions. Discrete Applied Mathematics 158: 755-764 (2010)
- Daniel Lokshtanov. On the complexity of computing treelength. Discrete Applied Mathematics 158: 820-827 (2010)
- M. Fellows, B. Jansen, D. Lokshtanov, Fran Rosamond, Saket Saurabh. Determining the winner of a Dodgson election is hard. FSTTCS 2010
2009
Publications in 2009
- F. Cicalese, F. Manne, and Q. Xin, Faster Centralized Communication in Radio Networks. Algorithmica 54 (2): 226-242 (2009)
- Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil: A new self-stabilizing maximal matching algorithm. Theor. Comput. Sci. 410(14): 1336-1345 (2009)
- Alicia Thorsen, Phillip Merkey, Fredrik Manne: Maximum weighted matching using the partitioned global address space model. SpringSim 2009
- Jean R. S. Blair, Fredrik Manne: An Efficient Self-stabilizing Distance-2 Coloring Algorithm. SIROCCO 2009: 237-251
- Fredrik Manne, Md. Mostofa Ali Patwary: A Scalable Parallel Union-Find Algorithm for Distributed Memory Computers. PPAM (1) 2009: 186-195
- F. V. Fomin, S. Gaspers, S. Saurabh, and A. A. Stepanov. On Two Techniques of Combining Branching and Treewidth. Algorithmica 54(2):181-207 (2009)
- A. Bonato, P.A. Golovach, G. Hahn and J. Kratochvil, The capture time of a graph. Discrete Mathematics. 309(18): 5588-5595 (2009)
- F.V. Fomin, P.A. Golovach and D. Thilikos, Approximating acyclicity parameters of sparse hypergraphs. Proceedings of STACS 2009, p. 445-456.
- F.V. Fomin, P. A. Golovach, D. Lokshtanov, and S. Saurabh, Clique-width: on the price of generality. Proceedings of SODA 2009, ACM-SIAM, p. 825-83.
- S. Gaspers and G. B. Sorkin, A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between, Proceedings of SODA 2009, ACM and SIAM, p. 606-615.
- P. Heggernes and C. Papadopoulos. Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Theoretical Computer Science 410-1 (2009): 1-15.
- Y. Villanger, P. Heggernes, C. Paul, and J. A. Telle. Interval Completion is Fixed Parameter Tractable. SIAM Journal on Computing 38-5 (2009): 2007-2020.
- P. Heggernes, D. Meister, and C. Papadopoulos. A complete characterization of the linear clique-width of pathpowers, Proceedings of TAMC 2009, Springer LNCS 5532: 241-250 .
- P. Heggernes, D. Meister, and C. Papadopoulos. A new representation of proper interval graphs with an application to clique-width, Electronic Notes in Discrete Mathematics 32 (2009): 27-34.
- P. Heggernes and R. Mihai.Edge search number of cographs in linear time, Proceedings of FAW 2009, Springer LNCS.
- R. Mihai and I. Todinca. Pathwidth is NP-hard for weighted trees, Proceedings of FAW 2009, Springer LNCS.
- R.Mihai and M.Mjelde. A Self-Stabilizing Algorithm for Graph Searching in Trees, Proceedings of SSS 2009, Springer LNCS.
- P. Heggernes, F. Mancini, C. Papadopoulos, and R. Sritharan. Strongly chordal and chordal bipartite graphs are sandwich monotone, COCOON 2009, Springer LNCS.
- J. Nederlof. Fast polynomial-space algorithms using Möbius inversion: Improving on Steiner Tree and related problems, ICALP 2009.
- N. Alon, D. Lokshtanov, and S. Saurabh. Fast FAST, ICALP 2009.
- M. Dom, D. Lokshtanov, and S. Saurabh.Incompressibility through colors and IDs, ICALP 2009.
- P. Heggernes, F. Mancini. Dynamically maintaining split graphs. Discrete Applied Mathematics 157: 2057-2069 (2009).
- T. Ekim, P. Heggernes and D. Meister. Polar permutation graphs, Proceedings of IWOCA 2009, Springer LNCS.
- D. Meister and J. A. Telle, Chordal digraphs, Proceedings of WG 2009.
- F. Dorn, J. A. Telle. Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm. Discrete Applied Mathematics, 157: pages 2737-2746, 2009.
- Nathann Cohen, Fedor V. Fomin, Gregory Gutin, Eun Jung Kim, Saket Saurabh, Anders Yeo: Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem. COCOON 2009: 37-46
- Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos: Contraction Bidimensionality: The Accurate Picture. ESA 2009: 706-717
- Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos: (Meta) Kernelization. FOCS 2009: 629-638
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh: Subexponential Algorithms for Partial Cover Problems. FSTTCS 2009: 193-201
- Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, Stéphan Thomassé: Kernels for Feedback Arc Set In Tournaments. FSTTCS 2009: 37-47
- Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh: Distortion Is Fixed Parameter Tractable. ICALP (1) 2009: 463-474
- Omid Amini, Fedor V. Fomin, Saket Saurabh: Counting Subgraphs via Homomorphisms. ICALP (1) 2009: 71-82
- Michael R. Fellows, Frances A. Rosamond, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Local Search: Is Brute-Force Avoidable? IJCAI 2009: 486-491
- Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé: A Linear Vertex Kernel for Maximum Internal Spanning Tree. ISAAC 2009: 275-282
- Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, Daniël Paulusma: Three Complexity Results on Coloring Pk-Free Graphs. IWOCA 2009: 95-104
- B.M.Bui-Xuan, J.A.Telle, M.Vatshelle. Feedback Vertex Set on Graphs of low Cliquewidth. Proceedings IWOCA 2009, LNCS, 5874, pp. 113-124, 2009
- B.-M. Bui-Xuan and M. Habib. Unifying the representation of symmetric crossing families and weakly partitive families. European Conference on Combinatorics, Graph Theory and Applications (EuroComb'09), volume 34 of ENDM, pages 329--333, 2009
- B.-M. Bui-Xuan, M. Habib, and M. Rao. Representation theorems for two set families and applications to combinatorial decompositions. International Conference on Relations, Orders and Graphs: Interaction with Computer Science (ROGICS'08), Nouha editions, pages 532--546, 2008
- Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, Yngve Villanger: Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. STACS 2009: 421-432
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov: Guard Games on Graphs: Keep the Intruder Out! WAOA 2009: 147-158
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh: An Exact Algorithm for Minimum Distortion Embedding. WG 2009: 112-121
- Hajo Broersma, Fedor V. Fomin, Pim van 't Hof, Daniël Paulusma: Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. WG 2009: 44-53
- Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse: Nondeterministic Graph Searching: From Pathwidth to Treewidth. Algorithmica 53(3): 358-373 (2009)
- Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Sort and Search: Exact algorithms for generalized domination. Inf. Process. Lett. 109(14): 795-798 (2009)
- Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5): (2009)
- Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh: Spanning Directed Trees with Many Leaves. SIAM J. Discrete Math. 23(1): 466-476 (2009)
- Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar: The Budgeted Unique Coverage Problem and Color-Coding. CSR 2009: 310-321
- Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar: Simpler Parameterized Algorithm for OCT. IWOCA 2009: 380-384
- Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, Somnath Sikdar: On the Directed Degree-Preserving Spanning Tree Problem. IWPEC 2009: 276-287
- Daniel Lokshtanov, Saket Saurabh: Even Faster Algorithm for Set Splitting! IWPEC 2009: 288-299
- Daniel Lokshtanov, Matthias Mnich, Saket Saurabh: Linear Kernel for Planar Connected Dominating Set. TAMC 2009: 281-290
- Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh: The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. Theory Comput. Syst. 45(4): 822-848 (2009)
- Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos: Induced Packing of Odd Cycles in a Planar Graph. ISAAC 2009: 514-523
- Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh: Bandwidth on AT-Free Graphs. ISAAC 2009: 573-582
- Petr A. Golovach, Dimitrios M. Thilikos: Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. IWPEC 2009: 210-221
- Petr A. Golovach, Pinar Heggernes: Choosability of P5-Free Graphs. MFCS 2009: 382-391
- Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. TAMC 2009: 221-230
- Petr A. Golovach, Jan Kratochvíl, Ondrej Suchý: Parameterized Complexity of Generalized Domination Problems. WG 2009: 133-142
- Isolde Adler, Mark Weyer: Tree-Width for First Order Formulae. CSL 2009: 71-85
- Pinar Heggernes and Federico Mancini. Minimal split completions. Discrete Applied Mathematics 157: 2659-2669 (2009)
- Jesper Nederlof, Johan M M van Rooij and Thomas van Dijk. Inclusion/exclusion meets measure and conquer. ESA 2009: 554-565
- Pinar Heggernes, Dieter Kratsch and Daniel Meister. Bandwidth of bipartite permutation graphs in polynomial time. Journal of Discrete Algorithms 7:533-544 (2009)
- Karol Suchan and Yngve Villanger. Computing pathwidth faster than 2^n. IWPEC 2009: 324-335
- Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman. An exact almost optimal algorithm for target selection in social networks. ACM conference on electronic commerce 2009: 355-362.
- B-M.Bui-Xuan, J.A.Telle and M.Vatshelle. Boolean-width of graph. Proceedings IWPEC 2009, LNCS, 5917, pp. 61-74, 2009
- Daniel Lokshtanov. Finding the longest isometric cycle in a graph. Discrete Applied Mathematics 157: 2670-2674 (2009)
2008
Publications in 2008
- C.Sloper, J.A.Telle, An overview of techniques for designing parameterized algorithms. The Computer Journal. 51(1): 122-136 (2008).
- J.Fiala, D.Paulusma, J.A.Telle, Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics. 29(4): 850-880 (2008)
- J.Fiala and P.A. Golovach, Complexity of the packing coloring problem for trees, Proceedings of WG 2008, Springer LNCS.
- J.Fiala, P.A. Golovach and J. Kratochvil, Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract), Proceedings of ICALP 2008, Springer-Verlag Lecture Notes in Computer Science, vol. 5125, 2008, pp. 294-305.
- J.Fiala, P.A. Golovach and J. Kratochvil, Distance Constrained Labeling of Trees, Proceedings of TAMC 2008, Springer-Verlag Lecture Notes in Computer Science, vol. 4978, 2008, pp. 125-135.
- P.A. Golovach and J. Kratochvil, Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity, Proceedings of TAMC 2008, Springer-Verlag Lecture Notes in Computer Science, vol. 4978, 2008, pp. 182-191.
- S. Gaspers, D. Kratsch, and M. Liedloff, On Independent Sets and Bicliques in Graphs, Proceedings of WG 2008, Springer LNCS.
- F.V. Fomin, P.A. Golovach, A. Hall, M. Mihalak, E. Vicari, and P. Widmayer, How to Guard a Graph?, Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008), Springer-Verlag Lecture Notes in Computer Science, vol. 5369, 2008, pp.318-329.
- M. Fellows, D. Meister, F. A. Rosamond, R. Sritharan, and J. A. Telle, Leaf Powers and Their Properties: Using the Trees, Proceedings of ISAAC 2008, Springer LNCS.
- F. Manne and R. Bisseling. A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem, In proceedings of The Seventh International Conference on Parallel Processing and Applied Mathematics (PPAM 2007), Springer LNCS 4967, pp. 708–717.
- F. Manne, M. Mjelde, Laurence Pilard, and Sebastien Tixeuil. A Self-Stabilizing 2/3 Approximation Algorithm for the Maximal Matching Problem. Proceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2008), Detroit, MI, USA, Springer LNCS.
- D. Bozdag, A. Gebremedhin, F. Manne, E. Boman, and U. Catalyurek. A framework for Scalable Greedy Coloring on Distributed Memory Parallel Computers. Journal of Parallel and Distributed Computing Vol 68, No 4 (2008), pages 515–535.
- F. Manne and Q. Xin Time Efficient Radio Broadcasting in Planar Graphs. Journal of Networks, Vol 3, No 2 (2008), pages 9–16.
- F. V. Fomin, F. Grandoni, A. Pyatkin, and A. Stepanov, Combinatorial Bounds via Measure and Conquer: Bounding Minimal Dominating Sets and Applications, ACM Transactions on Algorithms, 5(1), 2008, article 9.
- J. Chen, F. V. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved Algorithms for Feedback Vertex Set Problems. Journal of Computer and System Sciences 74, 2008, pp. 1188- 1198.
- F. V. Fomin, S. Gaspers, A. V. Pyatkin, and I. Razgon. On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica, 52 (2), 2008, pp. 293--307.
- F. V. Fomin, F. Grandoni and D. Kratsch. On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica, 52 (2), 2008, pp. 153-166.
- P. Heggernes, F. Mancini, and C. Papadopoulos. Minimal comparability completions of arbitrary graphs. Discrete Applied Mathematics 156 (2008), pages 705-718.
- F. V. Fomin, D. Kratsch, I. Todinca, and Y. Villanger. Exact algorithms for treewidth and minimum fill-in. SIAM Journal on Computing 38 (3), (2008), pp. 1058-1079.
- F. V. Fomin and D. M.Thilikos, An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, 399 (2008), pp. 236-245.
- F. Dorn, F. V. Fomin and D. M.Thilikos, Subexponential parameterized algorithms, Computer Science Review, 2 (2008), pp. 29-39
- P. Heggernes, D. Meister, C. Papadopoulos. Graphs of linear clique-width at most 3. Proceedings of TAMC 2008, Springer LNCS 4978, pages 330-341.
- P. Heggernes, D. Kratsch, and D. Meister. Bandwidth of bipartite permutation graphs in polynomial time. Proceedings of LATIN 2008, Springer LNCS 4957, pages 216-227.
- P. Heggernes and R. Mihai. Mixed search number of permutation graphs. Proceedings of FAW 2008, Springer LNCS 5059, pages 196-207.
- P. Heggernes, D. Meister, and A. Proskurowski. Computing minimum distortion embeddings into a path of bipartite permutation graphs and threshold graphs. Proceedings of SWAT 2008, Springer LNCS 5124, pages 331-342.
- P. Heggernes, D. Lokshtanov, R. Mihai, C. Papadopoulos. Cutwidth of split graphs, threshold graphs, and proper interval graphs. Proceedings of WG 2008, Springer LNCS.
- P. Golovach, Y. Villanger. Parameterized complexity for domination problems on degenerate graphs. Proceedings of WG 2008, Springer LNCS.
- H. Bodlaender, M. Fellows, P. Heggernes, F. Mancini, C. Papadopoulos and F. Rosamond. Clustering with partial information. Proceedings of MFCS 2008, Springer LNCS 5162, pages 144-155.
- F. V. Fomin, Y. Villanger. Treewidth computation and extremal combinatorics. Proceedings of ICALP 2008, Springer LNCS 5125, pages 597-608.
- F. Dragan, F. V. Fomin, and P. Golovach, Spanners in sparse graphs, Proceedings of ICALP 2008, Springer LNCS 5125, pages 597-608.
- F. V. Fomin, S. Gaspers, D. Kratsch, M. Liedloff, and S. Saurabh, Iterative Compression and Exact Algorithms, Proceedings of MFCS 2008, Springer LNCS 5162, pages 290-298.
- F. Dragan, F. V. Fomin, and P. Golovach, A PTAS for the sparsest spanners problem on apex-minor-free graphs, Proceedings of MFCS 2008, Springer LNCS 5162, pages 335--346.
- F. V. Fomin, F. Grandoni, and D. Kratsch, Faster Steiner Tree Computation in Polynomial-Space, Proceedings of ESA 2008, Springer LNCS 5193, pages 430-441.
- F. V. Fomin, P. Golovach, and J. Kratochvil, On tractability of Cops and Robbers game, Proceedings of TCS 2008, Springer Boston, Computer Science, vol. 237, pages 171-185.
- F. V. Fomin, J. Kratochvil, D. Lokshtanov, F. Mancini, and J. A. Telle, On the Complexity of Reconstructing H-free Graphs from their Star Systems, Proceedings of LATIN 2008, Springer LNCS 4957, pages 194-205.
- F. Dorn, F. V. Fomin and D. M. Thilikos, Catalan Structures and Dynamic Programming in H-minor-free graphs, Proceedings of SODA 2008, ACM and SIAM, pages 631-640.
- H. Bodlaender, P. Heggernes, and Y. Villanger, Faster parameterized algorithms for Minimum Fill-In, Proceedings of ISAAC 2008, Springer LNCS, to appear.
- F. V. Fomin, S.Saurabh and D. M. Thilikos, Improving the gap of Erdos-Posa property for minor closed graph classes, Proceedings of CTW 2008.
- S. Gaspers, S.Saurabh and A. Stepanov, A Moderately Exponential Time Algorithm for Full Degree Spanning Tree, Proceedings of TAMC 2008, Springer 4978, pages 479-489.
- V. Raman, S.Saurabh and S. Srihari, Parameterized Algorithms for Generalized Domination, Proceedings of COCOA 2008, Springer LNCS 5165, pages 116-126.
- O. Amini, I. Sau and S.Saurabh, Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem, Proceedings of IWPEC 2008, Springer LNCS 5018 , pages 13-29.
- M. Dom, D.Lokshtanov, S.Saurabh and Y.Villanger, Capacitated Domination and Covering: A Parameterized Perspective, Proceedings of IWPEC 2008, Springer LNCS 5018, pages 78-90.
- S. Mishra, V. Raman, S.Saurabh and S. Sikdar, Konig Deletion Sets and Vertex Covers Above the Matching Size, Proceedings of ISAAC 2008, Springer LNCS, to appear.
- M. Fellows, D.Lokshtanov, N Misra, F. Rosamond and S.Saurabh, Graph Layout problems Parameterized by Vertex Cover, Proceedings of ISAAC 2008, Springer LNCS, to appear.
- O. Amini, D. Peleg, S. Perennes, I. Sau and S.Saurabh, Degree-Constrained Subgraph Problems: Hardness and Approximation Results, Proceedings of WAOA 2008, Springer, to appear.
- P. Heggernes and D. Kratsch. Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic Journal of Computing 14 (2007): 87-108.(Printed in 2008.)
- P. Heggernes and B. Peyton. Fast computation of minimal fill inside a given elimination ordering. SIAM Journal on Matrix Analysis and Applications 30-4 (2008): 1424-1444
- A.Berry, E. Dahlhaus, P. Heggernes, and G. Simonet. Sequential and parallel triangulating algorithms for Elimination Game and new insights on Minimum Degree. Theoretical Computer Science 409-3 (2008): 601-616.
2007
Publications in 2007
- A. H. Gebremedhin, A. Tarafdar, F. Manne, and A. Pothen, New Acyclic and Star Coloring Algorithms With Application to Computing Hessians, SIAM Journal on Scientific Computing. Vol 29, No 3 (2007), pp. 1042-1072.
- C. Papadopoulos and C. Voglis. Drawing graphs using modular decomposition. Journal of Graph Algorithms and Applications 11, (2007), pp. 481-511.
- F. Manne and M. Mjelde. A Self-Stabilizing Weighted Matching Algorithm. Ninth International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2007), Springer LNCS, vol. 4838, pp. 383-393, 2007.
- Ted Herman, Sriram Pemmaraju, Laurence Pilard and M. Mjelde. Temporal Partition in Sensor Networks. Ninth International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2007), Springer LNCS, vol. 4838, pp. 325-339, 2007.
- F. Manne, M. Mjelde, Laurence Pilard, and Sebastien Tixeuil. A New Self-Stabilizing Maximal Matching Algorithm. The Colloquia on Structural Information and Communication Complexity (SIROCCO) 2007. In Springer LNCS 4474, pp. 96 -108, 2007.
- D. Meister, J.A. Telle, and M. Vatshelle. Characterization and recognition of digraphs of bounded Kelly-width. Proceedings of WG 2007, LNCS 4769, 2007.
- D. Meister. A characterisation of the minimal triangulations of permutation graphs. Proceedings of WG 2007, LNCS 4769, 2007.
- D. Meister. Polynomial-space decidable membership problems for recurrent systems over sets of natural numbers. Theory of Computing Systems 41, pp. 257-289, 2007.
- P. Heggernes, C. Paul, J. A. Telle, and Y. Villanger. Interval Completion with Few Edges, Proceedings of STOC 2007 - 39th ACM Symposium on Theory of Computing, June 2007, San Diego, USA. ACM press, pages 374-381.
- P. Heggernes, K. Suchan, I. Todinca, and Y. Villanger. Characterizing minimal interval completions: Towards better understanding of profile and pathwidth. Proceedings of STACS 2007 - 24th International Symposium on Theoretical Aspects of Computer Science. Springer LNCS 4393, pages 236-247.
- F.Manne, S.Wang and Q.Xin: Faster Radio Broadcast in Planar Graphs. Proceedings of WONS 2007 - 4th Annual Conference on Wireless On Demand Network Systems and Services, IEEE press, pp. 9-13.
- P. Heggernes and C. Papadopoulos. Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Proceedings of COCOON 2007 - 13th Annual International Computing and Combinatorics Conference. Springer LNCS 4598, pages 406-416.
- F. Fomin and A. Stepanov. Counting minimum weighted dominating sets. Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4598, 2007, pp. 65-74.
- F. Fomin, S. Gaspers and S. Saurabh. Improved Exact Algorithms for Counting 3- and 4- Colorings. Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4598, 2007, pp. 191-203.
- F. Fomin, P. Heggernes and R. Mihai. Mixed search number and linear-width of interval and split graphs. Proceedings of the 33d Workshop on Graph Theoretic Concepts in Computer Science (WG 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4769, 2007, pp. 304-315.
- F. Mancini, Minimum Fill-In and Treewidth of Split+ke and Split+kv Graphs. The 18th International Symposium on Algorithms and Computation (ISAAC 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4835, 2007, pp. 881-892.
- P.A. Golovach, J.Kratochvil, Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs, Proceedings of the 33d Workshop on Graph Theoretic Concepts in Computer Science (WG 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4769, 2007, pp. 1-11.
- M. Fellows, F.V. Fomin, D. Lokshtanov, F. Rosamond, S.Saurabh, S. Szeider and C. Thomassen, On the Complexity of Some Colorful Problems Parameterized by Treewidth}, Proceedings of the 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4616, 2007, pp.366-377.
- N. Alon, F.V. Fomin, G. Gutin, M. Krivelevich, and S. Saurabh, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Proceedings of the 27th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4855, 2007, pp. 316-327.
- F. Dorn. How to use planarity efficiently: new tree-decomposition based algorithms, Proceedings of the 33d Workshop on Graph Theoretic Concepts in Computer Science (WG 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4769, 2007, pp.
- N. Alon, F.V. Fomin, G. Gutin, M. Krivelevich, and S. Saurabh, Parameterized Algorithms for Directed Maximum Leaf Problems, Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4596, 2007, pp. 352-362.
- F. Dorn, F. V. Fomin, and D. M. Thilikos, Subexponential parameterized algorithms (invited talk), Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4596, 2007, pp. 15-27.
- J. Chen, F.V. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved Algorithms for the Feedback Vertex Set Problems, Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4619, 2007, pp.422-433.
- F.V. Fomin, P.A. Golovach, J. Kratochvil, D. Kratsch, M. Liedloff, Branch and Recharge: Exact algorithms for generalized domination, Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Springer-Verlag Lecture Notes in Computer Science, vol. 4619, 2007, pp.507-518.
- F.V. Fomin, P. Heggernes, and D. Kratsch, Exact algorithms for graph homomorphisms. Theory of Computing Systems 41 (2), (2007), pp. 381--393.
- H. Broersma, F.V. Fomin, P. Golovach, and G. J. Woeginger, Backbone colorings for graphs: tree and path backbones, Journal of Graph Theory, 55 (2), (2007), pp. 137-152.
- K. Asdre, S.D. Nikolopoulos and C. Papadopoulos, An optimal parallel solution for the path cover problem on P4-sparse graphs. Journal of Parallel and Distributed Computing, 67 (1) (2007), pages 63-76.
- L.H. Stien, A. Kiessling, and F. Manne, Rapid estimation of fat content in salmon fillets by colour image analysis Journal of Food Composition and Analysis, Journal of Food Composition and Analysis, No 20, (2007), pp. 73-79.
- H. Broersma, F. V. Fomin, R. Kralovic, and G. J. Woeginger, Eliminating graphs by means of parallel knock-out schemes, Discrete Applied Mathematics 155 (2), (2007), pp. 92-102.
2006
Publications in 2006
- F. Manne and M. Mjelde, A Memory Efficient Self-stabilizing Algorithm for Maximal k-packing, In Eighth Int. Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2006), Springer LNCS, vol. 4271, 2006, pp. 428-439.
- L.H. Stien, F. Manne, K. Ruohonene, A. Kause, K. Rungruangsak-Torrissen, and A. Kiessling, Automated image analysis as a tool to quantify the colour and composition of rainbow trout (Oncorhynchus mykiss W.) cutlets, Aquaculture, 261 (2), (2006), pp. 695-705
- Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006 Bergen, Norway, June 22-23, 2006 Revised Papers, Fomin, Fedor V. (Ed.), Springer-Verlag Lecture Notes in Computer Science, vol. \ 4271, 2006.
- F. V. Fomin and D. M. Thilikos, A 3-approximation for the pathwidth of Halin graphs, Journal of Discrete Algorithms 4 (4), (2006), pp. 499--510
- F. V. Fomin and D. M. Thilikos, Dominating sets in planar graphs: branch-width and exponential speed-up, SIAM Journal on Computing 36 (2), (2006), pp. 281-ﾖ309
- F. V. Fomin, F. Grandoni, and D. Kratsch, Solving Connected Dominating Set Faster than O (2n), Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2006), Springer LNCS vol. 4337, 2006, pp. 152-163.
- F. V. Fomin, S. Gaspers, and S.Saurabh, Branching and treewidth based exact algorithms, Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), Springer LNCS, vol. 4288, 2006, pp. 16-25.
- H. L. Bodlaender, F. V. Fomin, A. M. C. A. Koster, D. Kratsch, and D. M. Thilikos, On exact algorithms for treewidth, Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), Springer LNCS, vol. 4168, 2006, pp.672-683.
- D.Wood, J.A.Telle, Planar decompositions and the crossing number of graphs with an excluded minor. Proceedings Graph Drawing 2006. LNCS. To appear.
- C.Sloper, J.A.Telle, Towards a taxonomy of techniques for designing parameterized algorithms. Proceedings IWPEC 2006. LNCS 4169, pp. 251-264.
- Y. Villanger. Improved exponential-time algorithms for treewidth and minimum fill-in. Proceedings of Latin American Theoretical Informatics Symposium (LATIN 2006), Springer LNCS 3887, pp. 800 - 811.
- P. Heggernes and F. Mancini. Minimal split completions of graphs. Proceedings of Latin American Theoretical Informatics Symposium (LATIN 2006), Springer LNCS 3887, pp. 592 - 604.
- F. Dorn and J.A. Telle. Two birds with one stone: the best of branchwidth and treewidth with one algorithm. Proceedings of 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Springer LNCS 3887, pages 386-397
- F. V.Fomin, F. Grandoni, and D. Kratsch, Measure and Conquer: A Simple O(20.288n) Independent Set Algorithm, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), {ACM and SIAM}, 2006, pp. 18-25.
- A. Berry, J-P.Bordat, P. Heggernes, G. Simonet, and Y. Villanger, A wide-range algorithm for minimal triangulation from an arbitrary ordering. Journal of Algorithms 58-1 (2006), pages 33 - 66.
- H. Broersma, F. V. Fomin, J. Kratochvil, and G. J.Woeginger, Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult, Algorithmica 44 (4), (2006), pp. 343-361.
- F. V. Fomin and K. Høie , Pathwidth of cubic graphs and exact algorithms, Information Processing Letters, 97 (5), (2006), pp. 191-196.
- F. V. Fomin and D. M.Thilikos, New upper bounds on the decomposability of planar graphs, Journal of Graph Theory, 51 (1), (2006), pp. 53-81
- P. Heggernes, Minimal triangulations of graphs: A survey. Discrete Mathematics, 306 (3) (2006), pp. 297-317.
- A. Berry, P. Heggernes, and Y. Villanger. A vertex incremental approach for maintaining chordality. Discrete Mathematics, 306 (3) (2006), pp 318-336.
- Y. Villanger. Lex-M versus MCSM. Discrete Mathematics, 306 (3) (2006), pp. 393-400.
- S. Gaspers and M. Liedloff. A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs. Proceedings of the 32nd Workshop on Graph Theoretical Concepts in Computer Science (WG 2006).
- S.D. Nikolopoulos, L. Palios and C. Papadopoulos. A Fully Dynamic Algorithm for the Recognition of P4-sparse Graphs. Proceedings of the 32nd Workshop on Graph Theoretical Concepts in Computer Science (WG 2006), Springer LNCS 4271, pp. 256 - 268.
- C. Paul, A. Proskurowski and J. A. Telle. Generation of edge-maximal graphs with bounded branchwidth. Proceedings of the 32nd Workshop on Graph Theoretical Concepts in Computer Science (WG 2006).
- S. Gaspers, D. Kratsch, and M. Liedloff. Exponential time algorithms for the minimum dominating set problem on some graph classes. Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Springer LNCS 4059, pp. 148 - 159.
- F. Dorn, F. V. Fomin, and D. M. Thilikos. Fast subexponential algorithm for non-local problems on graphs of bounded genus.Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Springer LNCS 4059, pp. 172-183.
- F. V. Fomin, S. Gaspers, and A. V. Pyatkin. Finding a Minimum Feedback Vertex Set in time O(1.7548n). Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006) Springer LNCS 4169, 2006, pp.184-191.
- F. Dorn. Dynamic Programming and Fast Matrix Multiplication. Proceedings of 14th Annual European Symposium (ESA 2006), Springer LNCS 4168, pages 280-291 .
- F. Manne, and Q. Xin. Optimal Gossiping with Unit Size Messages in Known Radio Networks. Proceedings of the 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006), Springer LNCS 4235, pp. 125-134.
- J. Cohen, F. V. Fomin, P. Heggernes, D. Kratsch, and G. Kucherov. Optimal linear arrangement of interval graphs. Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Springer LNCS 4162, pages 267-279.
- P. Heggernes, F. Mancini, and C. Papadopoulos. Making arbitrary graphs transitively orientable: Minimal comparability completions. Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Springer LNCS 4288, pages 419 - 428.
- F.Cicalese, F. Manne, and Q. Xin, Faster Centralized Communication in Radio Networks. Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Springer LNCS 4288, pages 339-348.
- S.D. Nikolopoulos and C. Papadopoulos, On the number of spanning trees of $K_n^m \pm G$ graphs. Discrete Mathematics & Theoretical Computer Science 8 (2006), pages 235 - 248.
- P. Heggernes and D. Lokshtanov. Optimal broadcast domination in polynomial time. Discrete Mathematics 306-24 (2006), pages 3267 - 3280.
2005
Publications in 2005
- C. Voglis and C. Papadopoulos, Drawing graphs using modular decomposition. Proceedings of 13th Int'l Symposium on Graph Drawing (GD'05), Springer LNCS 3843, pp. 343 - 354.
- A. H. Gebremedhin, F. Manne, and A. Pothen, What Color is Your Jacobian? Graph Coloring for Computing Derivatives. SIAM Rieview, Vol 47, No 4, pp 629-705, 2005.
- E. Prieto and C. Sloper , Reducing to Independent Set Structure -- the Case of k-Internal Spanning Tree, Nordic Journal of Computing, 2005, volume 12, number 3, pp. 308-318
- D. Lokshtanov, C. Sloper , Fixed Parameter Set Splitting, Linear Kernel and Improved Running Time, In the Proceedings of ACID 2005.
- F. Manne and E. G. Boman, Balanced greedy colorings of sparse random graphs. Proceedings of NIK'2005, The Norwegian Informatics Conference, pp. 113-124.
- E. G. Boman, D. Bozdag, U. Catalyurek, A. H. Gebremedhin, and F. Manne, A Scalable Parallel Graph Coloring Algorithm for Distributed Memory Computers. Proceedings of 11th International Conference on Parallel and Distributed Computing (Europar 2005), Springer LNCS 3648, pp. 241 - 251.
- D. Bozdag, U. Catalyurek, A. H. Gebremedhin, F. Manne, E. G. Boman, and F. Ozguner, A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers. Proceedings of The 2005 International Conference on High Performance Computing and Communications (HPCC 05), Springer LNCS 3726, pp. 796 - 806.
- P. Heggernes, J. A. Telle, and Y. Villanger, Computing Minimal Triangulations in Time O(nα log n) = o(n2.376) . Proceedings of SODA 2005 - ACM-SIAM Symposium on Discrete Algorithms, pp. 907-916.
- F. V. Fomin, F. Grandoni, and D. Kratsch, Some new techniques in design and analysis of exact (exponential) algorithms, Bulletin of the European Association for Theoretical Computer Science 87, October 2005, pp.47-77
- F. V. Fomin, F. Mazoit, and I.Todinca, Computing branchwidth via efficient triangulations and blocks, Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005), Springer LNCS vol. 3787, 2005, pp. 374-384.
- P. Heggernes and D. Lokshtanov, Optimal broadcast domination of arbitrary graphs in polynomial time. Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005), Springer LNCS.
- J.Fiala, D.Paulusma and J.A.Telle, Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms, Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005), Springer LNCS.
- C.Paul and J.A.Telle, Edge-maximal graphs of branchwidth k Proceedings of ICGT'05, 7th International Colloquium on Graph Theory, Electronic Notes in Discrete Mathematics vol 22, 363-368
- F. V. Fomin, F. Grandoni, A. Pyatkin, and A. Stepanov, Bounding the Number of Minimal Dominating Sets: a Measure and Conquer Approach, Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), Springer LNCS, vol. 3827, 2005, pp. 573-582.
- F.V. Fomin, P. Heggernes, and D. Kratsch, Exact algorithms for graph homomorphisms. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Springer LNCS 3623, pp. 161-171.
- P. Heggernes, K. Suchan, I. Todinca, and Y. Villanger, Minimal interval completions. Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Springer LNCS 3669, pp. 403 - 414.
- C. Paul and J. A. Telle, New tools and simpler algorithms for branchwidth. Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Springer LNCS 3669.
- F. Dorn, E. Penninkx, H. Bodlaender, and F.V.Fomin, Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions, Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005),Springer LNCS, vol. 3669, 2005, pp.95-106.
- F. V. Fomin, P. Fraigniaud, and N. Nisse, Nondeterministic Graph Searching: From Pathwidth to Treewidth, Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005),Springer LNCS, vol. 3618, 2005, pp. 364-375.
- J.Fiala, D.Paulusma and J.A.Telle, Matrix and graph orders derived from locally constrained graph homomorphisms, Proceedings MFCS'05, 30th International Symposium on Mathematical Foundations of Computer Science, Springer LNCS
- F. V. Fomin, F. Grandoni, and D. Kratsch, Measure and Conquer: Domination -- A Case Study, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005),Springer LNCS, vol. 3580, 2005, pp. 191-203.
- J. Alber, F. Dorn, and R. Niedermeier, Experimental Evaluation of a Tree Decomposition Based Algorithm for Vertex Cover on Planar Graphs. Discrete Applied Mathematics, 145 (2) , (2005), pp.219-231.
- H. L. Bodlaender and F. V. Fomin, Equitable colorings of bounded treewidth graphs. Theoretical Computer Science, 340 (1) , (2005), pp.22-30.
- H. L. Bodlaender and F. V. Fomin, Tree decompositions with small cost. Discrete Applied Mathematics, 145 (2) , (2005), pp.143-154.
- E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M.Thilikos, Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs, ACM Transactions on Algorithms (TALG), 1 (1), (2005), pp. 33--47.
- E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M.Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM, 52 (6), (2005), pp. 866--893.
- J.A.Telle, Tree-decompositions of small pathwidth. Discrete Applied Mathematics, 145 (2) , (2005), pp.210-218.
- P. Heggernes, J. A. Telle, and Y. Villanger, Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). SIAM Journal on Discrete Mathematics, 19 (4), (2005), pp. 900 - 913.
2004
Publications in 2004
- H.Bodlaender and J. A. Telle, Space-efficient construction variants of dynamic programming Nordic Journal of Computing 11, 374-385, 2004
- F. Fomin, P. Heggernes, and J. A. Telle, Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica 41-2 (2004), pp 73 - 87.
- E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M.Thilikos, Bidimensional Parameters and Local Treewidth. SIAM Journal on Discrete Mathematics 18 (3), (2004), pp.501--511.
- J. Fiala, A. V. Fishkin, and F. V. Fomin, On distance constrained labeling of disk graphs. Theoretical Computer Science 326 (1-3), (2004), pp. 261-292.
- H. L. Bodlaender, H. Broersma, F. V. Fomin, A. V. Pyatkin, and G. J. Woeginger, Radio labeling with preassigned frequencies. SIAM Journal on Optimization 15 (1), (2004), pp.1-16.
- J. Blair, P. Heggernes, S.Horton, and F. Manne, Broadcast Domination Algorithms for Interval Graphs, Series-Parallel Graphs. Congressus Numerantium 169 (2004), pp. 55-77.
- J. Blair and F. Manne, Efficient Generic Multi-stage Self-stabilizing algorithms for trees. Proceedings of PDCS04, pp 333--338.
- A. Gebremedhin, F. Manne, and T. Woods, Speeding up parallel graph coloring. Proceedings of Para04, Springer LNCS 3732, pp. 1079 -- 1088.
- E. Prieto and C.Sloper , Looking at the Stars. Proceedings of IWPEC04, Springer LNCS.
- H. L. Bodlaender and F. V. Fomin, Equitable colorings of bounded treewidth graphs. Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Springer LNCS, vol. 3153, 2004, pp.180-190.
- H. Broersma, F. V. Fomin, and G. J. Woeginger, Parallel knock-out schemes in networks. Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Springer LNCS, vol. 3153, 2004, pp. 204-214.
- F. V. Fomin and D. M.Thilikos, Fast parameterized algorithms for graphs on surfaces. Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Springer LNCS, vol. 3142, 2004, pp. 581-592.
- F. V. Fomin, D. Kratsch, and I. Todinca, Exact (exponential) algorithms for treewidth and minimum fill-in. Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Springer LNCS, vol. 3142, 2004, pp.568-580.
- F. V. Fomin, M. Matamala, E. Prisner, and I. Rapaport, AT-free graphs: linear bounds for the oriented diameter. Discrete Applied Mathematics 141 (1-3), (2004), pp. 135-148.
- F. V. Fomin, D. Kratsch, and G. J. Woeginger, Exact (exponential) algorithms for the dominating set problem. Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science (WG 2004), Springer LNCS vol. 3353, 2004, pp.245-256.
- M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, and J. A. Telle, Finding k disjoint triangles in an arbitrary graph. Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science (WG 2004), Springer LNCS, vol. 3353, 2004, pp.235-245.
- F. V. Fomin and D. M. Thilikos, A Simple and Fast Approach for Solving Problems on Planar Graphs. Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Springer LNCS, vol. 2996, 2004, pp.56-67.
- E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos. Bidimensional Parameters and Local Treewidth, Proceedings of the 6th Latin American Theoretical INformatics Symposium (LATIN 2004), Springer LNCS, vol. 2976, 2004, pp. 109-118.
- P. Heggernes and Y. Villanger, Modifying a given elimination ordering to reduce fill. Proceedings PARA 2004 Workshop on State-of-the-Art in Scientific Computing, Springer Verlag, LNCS 3732, pp 788 - 797.
- F. V. Fomin, M. Matamala, and I. Rapaport, The complexity of approximating the oriented diameter of chordal graphs. J. Graph Theory 45 (4) (2004), pp. 255 - 269.
- E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos, Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 823-832.
- A. Berry, J. R. S. Blair, P. Heggernes, and B. W. Peyton. Maximum Cardinality Search for Computing Minimal Triangulations of Graphs. Algorithmica 39-4 (2004), pages 287 - 298.
- F. V. Fomin, D. Kratsch and H. Muller, Algorithms for graphs with small octopus, Discrete Appl. Math. 134 (1-3) (2004), pp. 105-128.
- F. V. Fomin, Searching expenditure and interval graphs, Discrete Appl. Math., 135 (2004), pp. 97-104.
- S.M.Hedetniemi, S.T.Hedetniemi, A.McRae, D.Parks and J.A.Telle, Iterated coloring, Discrete Math. 278 (1-3) (2004), pp. 81-108
- C.Sloper, An Eccentric Coloring of Trees, Australasian Journal of Combinatorics, Vol. 29 (2004), p309-322
- M.Bezem, T.Langholm, C.Sloper, Reverse engineering of Formal Languages using Testsets, Grammars 7(special issue):111-123, 2004.
- C.Cotta, P.Moscato, C.Sloper, Evolutionary search of thresholds for robust feature set selection: application to the analysis of microarray data, Applications of Evolutionary Computing, G. Raidl et al. (eds.), Lecture Notes in Computer Science 3005(2004), pp. 21-30
2003
Publications in 2003
- J. Fiala, P. Heggernes, P. Kristiansen, and J. A. Telle. Generalized H-coloring and H-covering of Trees. Nordic Journal of Computing 10 (3) (2003), pages 206-224.
- A. Berry, P. Heggernes, and Y. Villanger. A vertex incremental approach for dynamically maintaining chordal graphs. Proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC 2003), Springer LNCS, vol. 2906, 2003, pp. 47-57.
- A. Berry, P. Heggernes, and G. Simonet. The Minimum Degree Heuristic and the Minimal Triangulation Process, Proceedings WG 2003 - 29th Workshop on Graph Theoretic Concepts in Computer Science, June 2003, Elspeet, the Netherlands. Springer Verlag, Lecture Notes in Computer Science 2880, pages 58 - 70.
- A.Gebremedhin, I.Guerrin, J.Gustedt and J.A.Telle. Graph coloring on a coarse grained multiprocessor. Discrete Appl. Math. 131 (1), (2003) pp. 179-198.
- F. V. Fomin and D. M. Thilikos, On the Monotonicity of Games Generated by Symmetric Submodular Functions, Discrete Appl. Math. 131 (2) (2003), pp. 323-335.
- F. V. Fomin and P. A. Golovach, Interval degree and bandwidth of a graph, Discrete Appl. Math., 129 (2-3) (2003), pp. 345-359.
- F. V. Fomin, Pathwidth of planar and line graphs, Graphs and Combinatorics, 19 (1) (2003), pp. 91-99.
- F. V. Fomin, D. Kratsch, and H. Muller, On a domination search number, Discrete Appl. Math., 127 (3) (2003), pp. 565-580.
- F. V. Fomin and D. M. Thilikos, Dominating sets and local treewidth , In the proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003), Springer-Verlag Lecture Notes in Computer Science, vol.\ 2832, 2003, pp. 221-229.
- H. Broersma, F. V. Fomin, P. A. Golovach, G. J. Woeginger, Backbone colorings for networks , In the proceedings of the 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003), Springer-Verlag Lecture Notes in Computer Science. vol.\ 2880, 2003, pp. 131-142.
- F. V Fomin, P. Heggernes, and J. A. Telle, Graph searching, elimination trees, and a generalization of bandwidth, In the proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Springer-Verlag Lecture Notes in Computer Science vol.\ 2751, 2003, pp. 73-85.
- E. D. Demaine, F. V Fomin, M. T. Hajiaghayi, and D. M. Thilikos, Fixed-Parameter Algorithms for the $(k,r)$-Center in Planar Graphs and Map Graphs , In the proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Springer-Verlag Lecture Notes in Computer Science, vol.\ 2719, 2003, pp. 829-844.
- F. V Fomin and D. M. Thilikos, Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up , Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 168-177, ACM, New York, 2003.
- M.Halldorsson, G.Korsatz, A.Proskurowski, R.Salman, H.Shachnai and J.A.Telle Multi-coloring Trees, Information and Computation 180 (2003), 113-129, 2003
- J.Gustedt and J.A.Telle, A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set, Proceedings of the 10th Italian Conference on Theoretical Computer Science (ICTCS 2003), 2003, Springer Verlag, Lecture Notes in Computer Science, vol. 2841, pp. 125-136.
- E.Prieto, C. Sloper, Either/Or: Using Vertex Cover Structure in designing FPT-algorithms - the case of k-Internal Spanning Tree, Proceedings of Workshop on Algorithms and Data Structures (WADS 2003), 2003 Ottawa, LNCS vol 2748, pp 465-483
- J.Blair and F. Manne, Efficient Self-stabilzing Algorithms for Tree Networks, Proceedings of ICDS 2003, The 23rd IEEE International Conference on Distributed Computing Systems, pp 20-26. May 19-22, 2003 Providence, Rhode Island, USA. IEEE Press.
2002
Publications in 2002
- P. Heggernes and Y. Villanger. Efficient Implementation of a Minimal Triangulation Algorithm. Proceedings ESA 2002 - 10th European Symposium on Algorithms, Rome, Italy, September 2002. Springer Verlag, Lecture Notes in Computer Science 2461, pages 550-561.
- A. Berry, J. R. S. Blair, and P. Heggernes. Maximum Cardinality Search for Computing Minimal Triangulations. Proceedings WG 2002 - 28th Workshop on Graph Theoretical Concepts in Computer Science, Cesky Krumlov, Czech Rebublic, June 2002. Springer Verlag, Lecture Notes in Computer Science 2573, pages 1-12.
- J. Fiala, P. Heggernes, P. Kristiansen, and J. A. Telle. Generalized H-coloring and H-covering of Trees. Proceedings WG 2002 - 28th Workshop on Graph Theoretical Concepts in Computer Science, Cesky Krumlov, Czech Rebublic, June 2002. Springer Verlag, Lecture Notes in Computer Science 2573, pages 198-210.
- H. Broersma, F. V. Fomin, J. Nesetril and G. J. Woeginger , More about subcoloring, Computing 69 (2002) 3, pp. 187-203.
- F. V. Fomin, D. Kratsch, and J. C. Novelli, Approximating minimum cocolourings, Inform. Process. Lett. 84 (2002), no. 5, pp. 285-290.
- H. L. Bodlaender and F. V. Fomin, Approximation of pathwidth of outerplanar graphs, J. of Algorithms, 43 (2002), pp. 190-200.
- F. V. Fomin and A. Lingas, Approximation algorithms for time-depending orienteering, Inform. Proc. Letters. 83 (2) (2002), pp. 57-62.
- H. L. Bodlaender, H. Broersma, F. V. Fomin, A. V. Pyatkin, and G. J. Woeginger , Radio labeling with pre-assigned frequencies , Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), R. M\"ohring (Ed.): Springer-Verlag Lecture Notes in Computer Science, vol.\ 2461, 2002, pp. 211-222.
- H. Broersma, F. V. Fomin, J. Nesetril, and G. J. Woeginger , More about subcoloring , Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), L. Ku\v cera (Ed.): Springer-Verlag Lecture Notes in Computer Science, vol.\ 2573, 2002, pp. 68-79.
- F. V. Fomin, M. Matamala, and I. Rapaport , The complexity of approximating the oriented diameter of chordal graphs , Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), L. Ku\v cera (Ed.): Springer-Verlag Lecture Notes in Computer Science, vol.\ 2573, 2002, pp. 211-222.
- H. L. Bodlaender and F. V. Fomin , Tree decompositions with small cost, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002), M. Penttonen, E. Meineche Schmidt (Eds.): Springer-Verlag Lecture Notes in Computer Science, vol.\ 2368, 2002, pp. 378-387.
- H. Broersma, F. V. Fomin, J. Kratochvil, and G. J. Woeginger , Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous , Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002), M. Penttonen, E. Meineche Schmidt (Eds.): Springer-Verlag Lecture Notes in Computer Science, vol.\ 2368, 2002, pp. 160-169.
- A.Gebremedhin, I.Guerrin, J.Gustedt and J.A.Telle, PRO: A model for Parallel Resource-Optimal computation, Proceedings HPCS'2002 - The 16th Annual International Symposium on High Performance Computing Systems and Applications, IEEE, Moncton, NB, Canada, June 17-19, 2002.
- J.Gustedt, O.Mæhle and J.A.Telle , The treewidth of Java programs, Proceedings ALENEX'02- 4th Workshop on Algorithm Engineering and Experiments, San Francisco, January 4-5, 2002, Springer Verlag, Lecture Notes in Computer Science vol 2409.
- A.H.Gebremedhin, F.Manne, and A.Pothen, Parallel Distance-k Coloring Algorithms for Numerical Optimization, Proceedings Euro-Par 2002 - Paderborn, Germany, August 27-30, 2002, Springer Verlag, Lecture Notes in Computer Science vol 2400, pp. 912-921.
before 2002
For publications before 2002, please check the home pages of the group members.
31.07.2018