Algorithms seminar series
Seminaret bygger på INF234 og INF334, og er åpent for alle. I seminaret diskuteres aktuelle tema og siste nytt innen algoritmeforskning. Algoritmegruppens medlemmer presenterer jevnlig sitt arbeid. Dette er et forum der alle som er interessert i algoritmer og kompleksitet kan holde seg oppdatert.
Main content
2022
Autumn 2022
In charge of the seminars this semester is Kenneth Langedal
19.08.2022, Pranabendu Misra, Fixed-Parameter Semi-streaming Algorithms
26.08.2022, Ursula Hebert-Johnson, Counting and Sampling Labeled Chordal Graphs in Polynomial Time
02.09.2022, Vaishali Surianarayanan, Dominating set in weakly closed graphs is fixed parameter tractable
09.09.2022, Saket Saurabh, An FPT Approximation Scheme for the Maximum Coverage Problem
16.09.2022, Tuukka Korhonen, Computing Tree Decompositions with Small Independence Number
23.09.2022, Lars Jaffke, Taming graphs with no large creatures and skinny ladders
07.10.2022, Kenneth Langedal, PACE 2022 submission
21.10.2022, Tuukka Korhonen, Improved Parameterized Algorithm and Approximation Scheme for Treewidth
04.11.2022, Tanmay Inamdar, Tight FPT Approximations for Clustering Problems with Outliers
11.11.2022, Petr Golovach, Maximum Matchings in Frameworks
18.11.2022, Tomohiro Koana, The Complexity of Finding Fair Many-to-One Matchings
25.11.2022, Lars Jaffke, XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
02.12.2022, Pål Grønås Drange, PACE2023 update meeting
09.12.2022, Boris Djalal, Formalisation of a Newton Series Representation of Polynomials
Spring 2022
In charge of the seminars this semester is Farhad Vadiee
21.01.2022, Petr Golovach, Longest cycle above Erdös-Gallai bound.
28.01.2022, Fedor Fomin, Inconsistent Planning: When in doubt, toss a coin.
04.02.2022, Jan Arne Telle, A new Model of Machine Teaching.
11.02.2022, Petr Golovach, Detours in Directed Graphs.
25.02.2022, Tuukka Korhonen, Paths and Cycles of Large Rank in Frameworks.
04.03.2022, Paloma T. Lima, On the parameterized complexity of b-Coloring.
11.03.2022, Michael Ralph Fellows, PC and Some Heresies of Computational Complexity --- Old, Recent and Yet To Be Properly Explored.
18.03.2022, Ricardo Guimarães, Mining EL Bases with Adaptable Role Depth.
25.03.2022, Daniel Lokshtanov, A Quasi-Complete Classification of Classes with Few Minimal Separators.
08.04.2022, Kirill Simonov, Weighted Model Counting with Twin-Width.
22.04.2022, Matthias Mnich, Simple and fast high-multiplicity scheduling, and hints to the påskekrim.
29.04.2022, Clément Dallard, Tree decompositions with bounded independence number and their algorithmic applications.
29.04.2022, Dag Haugland, Bounds and solution methods for minimum broadcast time.
13.05.2022, Benjamin Bergougnoux, A Logic-Based Algorithmic Meta-Theorem for Mim-Width.
20.05.2022, Céline Swennenhuis, A Faster Exponential Time Algorithm for Bin Packing.
27.05.2022, Fahad Panolan, Partial Vertex Cover on Graphs of Bounded Degeneracy.
03.06.2022, Tuukka Korhonen, Grid Induced Minor Theorem for Graphs of Small Degree.
10.06.2022, Tanmay Inamdar, Non-Uniform k-Center and Greedy Clustering.
17.06.2022, Benjamin Bergougnoux, Recognition of Linear and Star Variants of Leaf Powers is in P.
2021
Autumn 2021
In charge of the seminars this semester is Emmanuel Arrighi
20.08.21, Fedor Fomin, Paths, Cycles and Beyond
27.08.21, Daniel Lokshtanov, A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane
03.09.21, Svein Høgemo, On Dasgupta's Clustering Objective and its Relation to Other Graph Parameters
10.09.21, Tuukka Korhonen, Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
17.09.21, Giannos Stamoulis, Block Elimination Distance
24.09.21, Emmanuel Arrighi, Order Reconfiguration under Width Constraints
01.10.21, Henning Fernau, Some Parameterized Complexity Results of Natural Combinatorial Problems in Automata Theory and Algebra
06.10.21, Petra Wolf, The Game of Cops and Robbers on Edge Periodic Temporal Graphs
15.10.21, Johannes Langguth, ML Accelerator Hardware: A General Model for Future Parallel Computation?
22.10.21, Emmanuel Arrighi, Order-Related Problems Parameterized by Width
29.10.21, Erlend Vagset, "Finding holes" or "The parameterized complexity of homology localization"
05.11.21, Farhad Vadiee, Dynamic Programming Refutations (PART I)
12.11.21, Srinivas Satti, Succinct representations for graph classes
Spring 2021
In charge of the seminars this semester is Fedor Fomin
Jan 15 Tanmay Inamdar Title: FPT Approximations for Constrained Sum-of-Radii Clustering
Jan 22 Benjamin Bergougnoux Linear Leaf Power Recognition is in P
Jan 29 Saket Saurabh An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
Feb 5 Petr Golovach: Parameterized Complexity of Directed Spanner Problems
Feb 12 Paloma Lima Reducing graph transversals via edge contractions
Feb 19 William Lochet EPTAS for k-means Clustering of Affine Subspaces
March 5 Mateus De Oliveira Oliveira From Dynamic Programming to Automated Theorem Proving
March 19 Nidhi Purohit Parameterized Complexity of Categorical Clustering with Size Constraints
2020
Autumn 2020 (heavy covid restrictions)
02.10.20, Emmanuel Arrighi, Graph Minors 13: The Disjoint Paths Problem
09.10.20, Benjamin Bergougnoux, Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width
16.10.20, Svein Høgemo, Hierarchical Clustering of Unweighted Graphs
Spring 2020
In charge of the seminars this semester is Svein Høgemo
January 31st Lars Jaffke, b-Coloring.
Feb 7 Jan Dreier Counting problems in sparse graphs.
Feb 14 Mateus de Oliveira Oliveira On the Width of Regular Classes of Finite Structures
Feb 21 Stefan Woltran Computational Argumentation -- Formal Models and Complexity Results
Feb 28 Olga Tveretina On the Reachability Problem for Low Dimensional Hybrid Automata
April 3 Fedor Fomin Subexponential parameterized algorithms on almost chordal graphs
April 17 Saket Saurabh Title: On the Complexity of Singly Connected Vertex Deletion
April 24 Mike Fellows Title “Some new results on 'the ultimate fpt classification tool' and work in progress"
May 8 Speaker: Sayan Bandyapadhyay Title: Improved Bounds for Metric Capacitated Covering Problems
May 15 Petr Golovach: Kernelization of Witney Switches
May 22 Speaker: Paloma Lima Title: Rainbow vertex coloring on graph classes
May 29 Speaker: William Lochet Title: Packing and covering balls in graphs excluding a minor
2019
Autumn 2019
The algorithms group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithms library and the seminar is in room 302O1.
In charge of the seminars is Kirill Simonov. Any question can be directed to Kirill (dot) Simonov (at) uib (dot) no
| 22. Nov | Benjamin Bergougnoux | Counting minimal transversal in beta-acyclic hypergraph |
| 15. Nov | Paloma Lima | Computational Social Choice, Trial Lecture |
| 08. Nov | Danil Sagunov | One more generalization of the proper coloring problem |
| 25. Oct | Kirill Simonov | Algorithms for graphs and geometric objects, Midway Assessment |
| 18. Oct | Geevarghese Philip | A 2-factor approximation algorithm for Feedback Vertex Set in tournaments |
| 11. Oct | Lars Jaffke | Typical Sequences Revisited - Computing Width Parameters of Graphs |
| 04. Oct | Nello Blaser | Algorithms in topological data analysis |
| 27. Sep | Torstein Strømme | Utilizing motivation: An extended version of the Scientist Grand Prix talk |
| 20. Sep | Paloma Lima | Reducing the domination number of graphs via edge contractions and vertex deletions |
| 06. Sep | Petr Golovach | Parameterized Low-Rank Binary Matrix Approximation |
| 30. Aug | Sayan Bandyapadhyay | On Perturbation Resilience of Non-Uniform k-Center |
Spring 2019
The algorithms group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithms library and the seminar is in room 302O1.
In charge of the seminars is Erlend Raa Vågset. Any question can be directed to Erlend (dot) Vagset (at) uib (dot) no
| 14. June | TBA | TBA |
| 07. June | WorKer | --- |
| 31. May | William Lochet | Domination in transitive tournaments |
| 24. May | Morten Brun | Density dependent persistent homology |
| 17. May | Constitution Day | --- |
| 13. May | Ferdinand Ihringer | A Construction for Cospectral Graphs. |
| 10. May | Pierre Fraigniaud | Distributed Interactive Proofs |
| 26. Apr | Topi Talvitie | Counting Linear Extensions in Practice |
| 23. Apr | Abhisekh Sankaran | Hereditariness in the finite and prefix classes offirst order logic |
| 19. Apr | Easter | --- |
| 12. Apr | Uéverton dos Santos Souza | Knot-free Vertex Deletion: A Deadlock Resolution Graph Problem |
| 05. Apr | Christophe Crespelle | On the effectiveness of the incremental approach to minimal chordal edge modification |
| 29. Mar | Benjamin Bergougnoux | Rank-based Approach on Graphs with Structured Neighborhood. |
| 22. Mar | Phan Thi Ha Duong | Interaction over time and fixed-parameter tractable algorithm on(Bi-)sparse split problem of graph. |
| 15. Mar | Winterschool | --- |
| 08. Mar | Charis Papadopoulos | Subset Feedback Vertex Set and Related Terminal Set Problems on Graphs of Bounded Independence Number |
| 01. Mar | Prafullkumar Tale | Graph Contraction Problems : Lossy Kernels and FPT algorithms |
| 22. Feb | Fahad Panolan | On the parameterized complexity of approximating dominating set |
| 15. Feb | Alexander S. Kulikov | Collapsing Superstring Conjecture |
| 01. Feb | Arnaud de Mesmay | Hard cutting problems on embedded graphs |
| 25. Jan | Olav Røthe Bakken | Graph Arrangement Problems Parameterized by Neighbourhood Diversity |
2018
Autumn 2018
The algorithms group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithms library and the seminar is in room 302O1.
In charge of the seminars is Eduard Eiben. Any question can be directed to Eduard (dot) Eiben (at) uib (dot) no.
| 2. Nov | Kirill Simonov | Parameterized Complexity of k-Means Clustering |
| 26. Oct | Petr Golovach | On the Parameterized Complexity of Graph Modification to First-Order Logic Properties |
| 19. Oct | Pratibha Choudhary | Tracking Set Problems |
| 12. Oct | Adam Kabela | Toughness and Hamiltonicity and using duality theorems |
| 5. Oct | William Lochet | Entropy compression and hypergraph orientation |
| 28. Sept | R. Vijayaragunathan | Facility location on Planar Graphs with Unreliable Links |
| 21. Sept | Sebastian Berndt | Computation of Treewidth -- Theory and Practice |
| 14. Sept | Pranabendu Misra | A brief note on Single Source Fault Tolerant Reachability |
| 7. Sept | Yijia Chen | Parameterized AC^0 -- some upper and lower bounds |
| 31. Aug | Carl Feghali | Paths between colourings of degenerate graphs |
Spring 2018
The algorithms group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithms library and the seminar is in room 302O1.
In charge of the seminars is Lars Jaffke. Any question can be directed to Lars (dot) Jaffke (at) ii (dot) uib (dot) no
| 15. Jun | Cèsar Ferri | Semi-Supervised Clustering Algorithms for Grouping Scientific Articles |
| 8. Jun | --- | --- |
| 1. Jun | Richard Fellows | Computation-Intensive Applications in Embedded System Design |
| 25. May | Christophe Crespelle | Faster and enhanced minimal cograph completion |
| 18. May | Jana Novotná | List 3-Colouring is polynomial for (P3+P4)- and (P2+P5)-free graphs |
| 11. May | Pranabendu Misra | Popular Matching in Roommates Setting is NP-hard |
| 04. May | Eduard Eiben | Lossy Kernels for Connected Dominating Set on Sparse Graphs |
| 27. Apr | --- | (Department Gathering) |
| 20. Apr | Mateus de Oliveira Oliveira | Complexity Measures for Permutation Groups |
| 13. Apr | Laurent Bulteau | The Clever Shopper Problem |
| 06. Apr | Danny Hermelin | New lower bounds for the Bicriteria Shortest Path problem |
| 30. Mar | --- | (Easter) |
| 23. Mar | --- | (Winter School) |
| 16. Mar | Reza Saei | Extremal Graph Theory, Turan and Ramsey Number |
| 09. Mar | Julie Meißner | Uncertainty Exploration for MST and Scheduling |
| 02. Mar | Dušan Knop | A Unifying Framework for Manipulation Problems |
| 23. Feb | Christophe Crespelle | Structures of Complex Networks and of their Dynamics |
| 16. Feb | Eduard Eiben | How to navigate through obstacles? |
| 09. Feb | Marika Ivanova | The shared multicast tree problem: tightening the LP bounds |
| 02. Feb | Tomáš Masařík | Local Dimension of Posets: Lower & Upper Bounds and Removable Theorems |
| 26. Jan | Frederic Dorn | Set-Based vs Procedural Approach --- or how to Optimize the Running Time of an Algorithm without Changing it |
| 19. Jan | Carl Feghali | Polynomial-Time Extensions of Brooks' Theorem |
2017
Autumn 2017
The algorithms group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithms library and the seminar is in room 302O1.
In charge of the seminars is Paloma Lima. Any question can be directed to Paloma (dot) Lima (at) ii (dot) uib (dot) no.
| 15. Dec | Daniel Lokshtanov | Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth |
| 08. Dec | -- | -- |
| 01. Dec | Amer Mouawad | A Theory of Change Through the Lens of Reconfiguration |
| 24. Nov | Bengt Aspvall | Analyzing QuickSelect in a Class Room Setting |
| 17. Nov | Akanksha Agrawal | Graph Modification Problems: Beyond the Known Boundaries (PhD Defense) |
| 10. Nov | Athanasios Konstantinidis | Strong Triadic Closure in Graph Classes |
| 03. Nov | Dusan Knop | Combinatorial n-fold Integer Programming and Applications |
| 27. Oct | Steven Chaplick | Constrained Recognition Problems on Geometric Graph Classes |
| 20. Oct | Krithika Ramaswamy | The Parameterized Complexity of Cycle Packing: Indifference is not an Issue |
| 13. Oct | Fahad Panolan | A Lower bound on Integer Programming |
| 06. Oct | Chhaya Dhingra | On the Convergence of Randomized Label Propagation |
| 29. Sept | Mohsen Alambardar Meybodi | Problems in Dominations and t-spanner graphs |
| 22. Sept | Sebastian Siebertz | A tutorial on uniform quasi-wideness |
| 15. Sept | Mateus Oliveira | Ground Reachability and Joinability in Linear Term Rewriting Systems are Fixed Parameter Tractable with Respect to Depth |
| 08. Sept | Roohani Sharma | Sub-exponential Fixed-Parameter Tractable Algorithm for Directed Feedback Arc Set in a Special Class of Digraphs |
| 01. Sept | Lars Jaffke | Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width |
| 25. Aug | Pranabendu Misra | Bipartite Perfect Matching is in quasi-NC |
| 18. Aug | Ivan Mihajlin | Irreducibility in fine-grained complexity |
2016
Autumn 2016
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 12.45, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Akanksha Agrawal. Any question can be directed to Akanksha (dot) Agrawal (at) ii (dot) uib (dot) no.
| 02. Dec | Marija Slavkovik | Judgment aggregation and its complexity |
| 25. Nov | Pranabendu Misra | Lossy Kernels for Graph Contraction Problems |
| 18. Nov | Pedro Montealegre | Parameterized algorithms via minimal triangulations and potential maximal cliques |
| 11. Nov | Christophe Crespelle | Linearity is Strictly More Powerful than Contiguity for Encoding Graphs |
| 04. Nov | Sanjukta Roy | Stable Matching Games: Manipulation via Subgraph Isomorphism |
28. Oct | Amer E. Mouawad | Packing Cycles Faster Than Erdős-Pósa |
21. Oct | Marcin Wrochna | Algorithms for graphs and matrices in poly(tw)*n time |
14. Oct | Bart M. P. Jansen | Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials |
07. Oct | Lars Jaffke | Fine-Grained Parameterized Complexity Analysis of Graph Coloring |
30. Sept | Mateus de Oliveira Oliveira | Tree-Zig-Zag Number of a digraph - Applications and Open Problems |
23. Sept | Md. Naim | Community Detection on GPU |
16. Sept | PrafullKumar P Tale | Dynamic Parameterized Problems |
| 02. Sept | Diptapriyo Majumdar | Structural Parameterizations of Feedback Vertex Set |
Spring 2016
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Torstein Strømme. Any questions can be directed to torstein (dot) stromme (at) ii (dot) uib (dot) no.
| Jun 10 | Fichte/Charwat | |
| Jun 8 (Wed) | Junjie Ye | |
| Jun 2 (Thur) | ||
| May 27 | O-joung Kwon | A single-exponential fixed parameter algorithm for Distance-Hereditary Vertex Deletion |
| May 20 | Daniel Lokshtanov | Lower bounds for approximation schemes for Closest String |
| May 13 | Sushmita Gupta | Stable matching games: Manipulation via graph connectivity |
| May 6 | Cancelled | |
| Apr 29 | Department gathering | |
| Apr 22 | Jan Arne Telle | |
| Apr 15 | Edvin Berglin | Applications of incidence in point covering problems |
| Apr 8 | Gunnar Fløystad | The interplay between graphs, simplicial complexes and ring theory |
| Apr 1 | Mithilesh Kumar | Component Order Connectivity |
| Mar 25 | Easter Vacation | |
| Mar 17 (Thur @ 14:15) | Mateus de Oliveira Oliveira | An Algorithmic Metatheorem for Graph Completion Problems |
| Mar 11 | Saket Saurabh | Communication Complexity of Pairs of Graph Families with Applications |
| Mar 4 | M. S. Ramanujan | A Linear Time Parameterized Algorithm for Feedback Vertex Set on Directed Graphs |
| Feb 26 | Fahad Panolan | Editing to Connected f-Degree Graph |
| Feb 19 | Michal Walicki | Kernels of Infinite Digraphs |
| Feb 12 | Petr Golovach | Parameterized Complexity of Secluded Connectivity Problems |
| Feb 5 | Daniel Lokshtanov | Below the Trivial Upper Bound for the Number of Minimal Connected Dominating Sets |
| Jan 29 | Cancelled | |
| Jan 22 | Erik Parmann | Case Studies in Constructive Mathematics (PhD defence) |
| Jan 15 | Damien Prot | From classical (for me) to classical (for you) tools in scheduling theory |
| Jan 8 | Tarek R. Besold | Like a Cognitive Walk in the Computational Park: Of Atom Models and Foldable Toothbrushes |
| Jan 6 | Kitty Meeks | When can an FPT decision algorithm be used to count? |
2015
Høstsemesteret 2015
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 12.45, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Md Naim. Any question can be directed to Md.Naim@uib.no
| 11. Dec | Magnus Wahlstrom | A combinatorial condition for FPT LP-branching |
| 04. Dec | Akanksha Agrawal | |
| 27. Nov | Daniel Lokshtanov | Parameterized Integer Quadratic Programming: Variables and Coefficients |
| 20. Nov | Amer Mouawad | Simultaneous Feedback Vertex Set: A Parameterized Perspective |
| 13. Nov | Jan Arne Telle | Recognizability equals definability for graphs of bounded treewidth and bounded chordality. |
| 06. Nov | No Seminar | |
| 30 Oct | No Seminar | |
23. Oct | Pål Grønås Drange | Empirical hardness models: focusing on instance distributions representative of practical applications rather than worst-case. |
19. Oct | Faisal Abu Khzam | The Multi-Parameterized Cluster Editing |
16. Oct | Markus Sortland Dregi | Compressing bounded degree graphs |
09. Oct | Pål Grønås Drange | Editing to starforests and bicluster graphs in subexponential time. |
02. Oct | Diptapriyo Majumdar | Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators |
30. Sept | Meriav Zehavi | Non-Standard Usage of the Method of Bounded Search Trees |
25. Sept | Torstein Strømme | "Structural" kernelization for Vertex Cover. |
| 18. Sept | No Seminar | |
| 11. Sept | Jan Arne Telle | Max-matching-width: new characterizations and a fast algorithm for dominating set |
Vårsemesteret 2015
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 13.00, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Fahad Panolan. Any question can be directed to Fahad.Panolan@ii.uib.no.
| 19.June | Pranabendu Misra | Deterministic Truncation of Linear Matroids |
| 12.June | Sudeshna Kolay | Parameterized Algorithms for deleting to (r,l)-graphs |
| 05.June | Marcin Wrochna | Recoloring graph homomorphisms using basic topology |
| 29. May | Reza Saei | PhD defence |
| 22. May | Prof. Igor Semaev | An application of combinatorics in cryptography |
20. May (at 2 PM) | Martin Koutecký | Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth |
15. May | No seminar | |
13. May (at 2 PM) | Kitty Meeks | Parameterised Subgraph Counting Problems |
| 08. May | No seminar | |
| 01. May | No seminar (Holiday) | |
| 24. April | Reza Saei | Graph spectra |
| 17. April | Jakub Gajarský | MSO Logic on Trees of Bounded Height |
| 10. April | Prof. Mike Fellow | FPT is Extremal Gradients: A Partial Preview of an ERC Proposal |
| 03. April | No seminar (Holiday) | |
| 27. March | Md. Naim | GPU architecture and Graph Algorithm |
| 20. March | Dieter Kratsch | Exact Exponential Algorithms |
| 13. March | Daniel Lokshtanov | Subset Feed Back Vertex Set in O(25.6^k(|V(G)|+|E(G)|)) time |
| 06. March | Petr Golovach | How to Hunt an Invisible Rabbit on a Graph |
| 27. February | Felix Reidl | Structural sparsity in the real world |
| 20. February | Markus S. Dregi | On the Computational Complexity of Vertex Integrity and Component Order Connectivity |
| 13. February | Rémy Belmonte | Induced Minor Free Graphs: Isomorphism and Clique-width |
| 06. February | Akanksha Agrawal | Vertex Cover on Delaunay Graphs |
| 30. January | M S Ramanujan | A parameterized complexity dichotomy for Boolean QCSP Deletion |
| 23. January | Petr Golovach | Editing to Eulerian Graphs |
| 16. January | Pål G. Drange | Editing to Threshold Graphs |
2014
Høstsemesteret 2014
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 12.45, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Mithilesh Kumar. Any question can be directed to Mithilesh.
| 12.dec | Christophe Crespelle | A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph With Regard to the Cartesian Product |
| 05.dec | Daniel Lokshtanov | Surprise !! |
| 28.nov | Saket Saurabh | Solving Multicut faster than 2^n |
| 21.nov | Kristina Vuskovic | Proof of the Confort-Rao Conjecture for linear balanced matrices |
| 14.nov | Isolde Adler | PAC learning of FO definable concepts & nowhere dense graph classes |
| 07.nov | No Seminar | |
| 31.oct | Sebastian Ordyniak | Backdoors into Heterogeneous Classes of SAT and CSP |
| 24.oct | Open Problems Session | |
| 17.oct | No Seminar | |
| 10.oct | Sigve Sæther | Between Treewidth and Clique-Width |
| 03.oct | Mithilesh Kumar | Faster Feedback Vertex Set in Tournaments |
| 26.sep | Amer Mouawad | Reconfiguration problems: Structure and tractability |
| 19.sep | Fahad P. | Faster FPT Algorithm for Eulerian Edge Deletion |
| 12.sep | Ashutosh Rai | On the kernelization complexity of String Problems |
| 05.sep | Reza Saei | Reconfiguration graphs and problems |
| 29. aug | Sandeep R.B. | On Polynomial Kernelization of H-free Edge Deletion |
| 22. aug | NA | No Seminar |
| 15. aug | Blair Sullivan | Bringing Theory to the Real World: is structural sparsity realistic? |
Vårsemesteret 2014
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 12.45, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Markus Dregi. Any question can be directed to markusdregi@gmail.com.
| 27. Juni | No seminar | |
| 20. Juni | Markus Dregi | Parameterized Complexity of Bandwidth on Trees. |
| 13. Juni | Michael R. Fellows | Parameterized Complexity AND Incremental Computing: some good news |
| 6. Juni | Daniel Lokshtanov | Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth |
| 30. May | No seminar | |
| 23. May | Alexey Stepanov | Applications of TSP in real life |
| 16. May | Fabrizio Grandoni | Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter |
| 9. May | Bart Jansen | |
| 2. May | No seminar | |
| 25. April | Rump Session | |
| 18. April | Easter | |
| 11. April | Marcin Pilipczuk | Online and dynamic algorithms for the Steiner tree problem. |
| 4. April | M S Ramanujan | Parameterized Algorithms to Preserve Connectivity. |
| 28. March | Sadia Sharmin | Graph Partitioning |
| 21. March | Winter school | |
| 14. March | Computing Treedepth | |
| 7. March | Erik Jan van Leeuwen | Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs |
| 28. February | Pål Grønås Drange | Subexponential Parameterized Complexity of Completion Problems |
| 21. February | Real algebraic geometry in computational game theory - a consumer's perspective | |
| 14. February | Sigve H Sæther | Domination Set parameterised by Clique-width |
| 7. February | Reza Saei | Finding Disjoint Paths in Split Graphs |
| 31. January | The r-simple k-path problem | |
| 24. January | Pinar Heggernes | Enumeration in Graph Classes |
| 17. January | Michał Pilipczuk | Minimum Bisection is FPT |
| 10. January | Manu Basavaraju | Partially Polynomial Kernels for SetCover and TestCover |
2013
Høstsemesteret 2013
Reza Saei was in charge of the seminars for this semester.
Vårsemesteret 2013
Thanks to Sigve Hortemo Sæther, for being in charge of the seminars for Spring semester.
| 14 June | Michał Pilipczuk | A polynomial kernel for Planar Steiner Tree parameterized by the size of the tree |
| 7 June | Dániel Marx | CSPs and fixed-parameter tractability |
| 31 May | Fredrik Manne | Efficient Sequential and Multicore Weighted Matching Algorithms |
| 24 May | Ondřej Suchý | On Explaining Integer Vectors by Few Homogenous Segments |
| 17 May | Norwegian Constitution Day | |
| 10 May | Mamadou Kanté | On the linear rank-width and linear clique-width of Trees |
| 3 May | Sadia Sharmin | Efficient Counting of Maximal Independent Sets in Sparse Graphs |
| 26 April | Arvid Lundervold | The role of graph theory and network analysis in quantitative neuroimaging |
| 19 April | Emilio Coppa | From asymptotics to performance profiling (and back) |
| 12 April | < No seminar > | |
| 5 April | M. S. Ramanujan | Backdoors to Satisfiability via q-horn formulas |
| 29 March | Easter holiday | |
| 22 March | Jean-François Couturier | A tight bound on the number of minimal dominating sets in split graph |
| 15 March | Dimitrios M. Thilikos | Polynomial gap extensions of the Erdős-Pósa theorem |
| 8 March | Henning Fernau | A multivariate analysis of pattern language problems |
| 1 March | Daniel Meister | Recent developments in clique-width computation |
| 22 February | Winter School 2013 | |
| 15 February | Rémy Belmonte | Graph rewriting |
| 8 February | Yixin Cao | Interval Deletion is Fixed-Parameter Tractable |
| 1 February | Rémy Belmonte | Induced Immersions |
| 25 January | Sven Simonsen | The complexity of finding arc-disjoint spanning trees and branchings in digraphs. FPT approach. |
| 18 January | Daniel Lokshtanov | Near-Tight Bounds for Cross-Validation via Loss Stability |
| 11 January | < No seminar > | |
2012
Høstsemesteret 2012
The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every Friday. We start with lunch at 12.00, and the seminar starts at 12.45, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.
In charge of the seminars is Pål Grønås Drange. Any question can be directed to Pal.Drange@ii.uib.no.
| 14 December | Archontia Giannopoulou | Lifo-search on (Di)graphs |
| 7 December | Pinar Heggernes | The maximum number of feedback vertex sets in chordal graphs and cographs |
| 5 December* | Hans Bodlaender | Connectivity problems on graphs of small treewidth |
| 30 November | Hans Bodlaender | Preprocessing and kernelization for Treewidth and Pathwidth |
| 23 November | Fedor V Fomin | Subexponential Parametrized Algorithm for Cluster Editing |
| 16 November | Reza Saeidinvar | Ramsey Numbers for Line Graphs and Perfect Graphs |
| 9 November | Erik Jan van Leeuwen | Parameterized Complexity of Induced H-Matching on Claw-Free Graphs |
| 2 November | Janne Korhonen | Counting in Halves and Fast Monotone Summation over Disjoint Sets |
| 26 October | Pim van 't Hof | On the parameterized complexity of finding separators with non-hereditary properties |
| 19 October | Ivan Bliznets | A new algorithm for parametrized MAX-SAT |
| 12 October | Daniel Lokshtanov | Polynomial Kernel for Planar F-Deletions |
| 5 October | Ignasi Sau | Parameterized domination in circle graphs |
| 28 September | Michał Pilipczuk | Randomized contractions |
| 21 September | Yngve Villanger | Searching for better fill-in |
| 14 September | Martin Vatshelle | The Point-Set Embeddability Problem for Plane Graphs |
| 7 September | Frederic Dorn | Short-term hydro scheduling from the algorithmic perspective |
| 3 September* | Bruce Reed | Catching a Drunk Miscreant |
| 31 August | Henning Fernau | Saving on Phases: Parameterized Approximation for Total Vertex Cover |
| 24 August | Rajesh Chitnis | Directed Multiway Cut is FPT |
| 17 August | Jan Arne Telle | FPT algorithms for domination in biclique-free graphs |
* means a special occasions seminar held outside of the general Friday seminar framework. 3rd of September, Bruce Reed visited our group in the occasion of Martin Vatshelle's PhD defence. He was so kind as to give a talk on recent work. 5th of December, during Hans Bodlaender's visit to Fedor Fomin's group, he gave a presentation of some of his recent work.
Vårsemesteret 2012
This semester our algorithms seminar is on Fridays, as usual.
In charge of the seminars is Rémy Belmonte.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (library).
| 22 May | Peter Golovach | Induced Disjoint Paths in AT-free Graphs |
| 8 June | Martin Vatshelle | Lower bounds on treewidth for practical computing (trial lecture) |
| 1 June | Mini-school on Width-Minors-Matroids | |
| 25 May | Arash Rafiey | Ordering without bad patterns |
| 11 May | Rémy Belmonte | Open problems session |
| 27 April | Michał Pilipczuk | On group feedback vertex set parameterized by the size of the cutset |
30 March | Igor Semaev | From Jacob Bernoulli to Modern Cryptography |
| 23 March | Bengt Aspvall | Sorting Algorithms As Special Cases Of A Priority Queue Sort |
| 16 March | Pim van 't Hof | Obtaining a Bipartite Graph by Contracting Few Edges |
| 9 March | Arash Rafiey | Homomorphism Problem and Approximation |
| 2 March | Michał Pilipczuk | Open problems session |
| 24 February | Finse | 10th Annual Winter School in Algorithms, Graph Theory, and Combinatorics |
| 17 February | Pål Grønås Drange | A randomized polynomial kernel for Odd Cycle Transversal |
| 10 February | Sigve H. Sæther | Broadcast domination on block graphs |
| 3 February | Martin Milanic | On the (in-)approximability and exact algorithms for vector domination and related problems in graphs |
| 20 January | Jean-Francois Couturier | Maximum number of minimal dominating sets in graph classes |
| 13 January | Erik Jan van Leeuwen | Algorithms for firefighting |
| 6 January | Daniel Lokshtanov | Faster Vertex Cover above LP |
2011
Høstsemesteret 2011
This semester our algorithms seminar is on Fridays, as usual.
In charge of the seminars is Jesper Nederlof.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (library).
| 16 December | Rémy Belmonte | Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths |
| 9 December, 10.15, Large Auditorium!! | Jesper Nederlof | Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms (PhD dissertation) |
| 2 December | Michał Pilipczuk | Solving the 2-Disjoint Connected Subgraphs problem faster than 2^n |
joint work with Marek Cygan, Marcin Pilipczuk and Jakub Onufry Wojtaszczyk Abstract The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z1, Z2 , asks whether it is possible to find disjoint sets A1, A2, such that Z1\subseteq A1, Z2\subseteq A2 and A1, A2 induce connected subgraphs. While the naive algorithm runs in O*(2^n) time, solutions with complexity of form O((2−eps)^n) have been found only for special graph classes. In the paper we present an O(1.933^n) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2^n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel. | ||
| 25 November, At 10.15, Small Auditorium!! | Jesper Nederlof | Property testing (Trial lecture) |
| 18 November | Henning Fernau | Parameterized Approximation Algorithms for Hitting Set |
| Abstract Several techniques have been developed over the years for (polynomial-time) approximation algorithms and for parameterized algorithms. We will show how to employ and combine some of these in order to obtain both new polynomial-time approximation algorithms for some types of Hitting Set problems as well as approximation algorithms that use exponential time in cases where polynomial-time algorithms with certain approximation guarantees are not to be expected under some complexity-theoretic assumptions. The polynomial-time algorithm that I will present is based on reduction rules, a technique primarily developed in the area of parameterized algorithms, while the (exponential-time) approximation algorithms combines ideas from approximation (namely, local ratio techniques) with search-tree algorithms. | ||
| 11 November | Daniel Paulusma | Lift Contractions |
Joint work with: Petr Golovach, Marcin Kaminski and Dimitrios Thilikos Abstract We introduce a new containment relation in graphs: lift contractions. We say that a graph H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. The edge lift operation is defined as follows. Let e=uv and e'=uw be two different edges incident with the same vertex u in a graph G. The lift of e and e' removes e and e' from G and then adds the edge vw if v and w are nonadjacent. We show that a graph contains every n-vertex graph as a lift contraction, if (1) its treewidth is large enough, or (2) its pathwidth is large enough and it is 2-connected, or (3) its order is large enough and its minimum degree is at least 3. | ||
| 4 November | Ruben van der Zwaan | Preemptive and Non-Preemptive Generalized Min Sum Set Cover |
| Abstract This talk is based on joint work with Sungjin Im and Maxim Sviridenko, where we give a 2-approximation for the Preemptive Generalized Min Sum Set Cover and use this to improve the current best approximation algorithm for Generalized Min Sum Set Cover. The problem was introduced by Azar, Gamzu and Yin, who gave a O(log n) approximation, which was improved by Bansal, Gupta and Krishnaswamy to roughly 500 and very recently to 28 by Skutella and Williamson.
In this talk I will motivate why this is an interesting problem to look at, for example both broadcast scheduling and web search ranking can be modelled as Generalized Min Sum Set Cover. Further, why it makes sense to look at the Preemptive version of the problem. I will not give proofs in this talk, I will just highlight the main ingredients needed to obtain this 2-approximation for the preemptive problem and later show how to transform this into a non-preemptive solution. At the end, I will possibly say something on generalizing this problem by using submodular cost functions, but only if time permits. | ||
| 28 October | Bart Jansen | Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization |
| Abstract In an informal blackboard-talk I will describe some results of a recent paper at ICALP, where we studied whether efficient preprocessing schemes for the Treewidth problem can give provable bounds on the size of the processed instances using the framework of kernelization. Assuming the AND-distillation conjecture to hold, the standard parameterization of Treewidth does not have a kernel of polynomial size and thus instances (G, k) of the decision problem of Treewidth cannot be efficiently reduced to equivalent instances of size polynomial in k. We therefore consider different (structural) parameterizations of the Treewidth problem. We show that Treewidth has a kernel with O(l^3) vertices, with l the size of a vertex cover, and a kernel with O(l^4) vertices, with l the size of a feedback vertex set. I will try to share some insights into how the reduction rules were found, and their relationship to experimental work on preprocessing heuristics for treewidth. We also obtained various kernel lower-bounds. Treewidth parameterized by the vertex-deletion distance to a co-cluster graph and Weighted Treewidth parameterized by the size of a vertex cover do not have polynomial kernels unless NP \subseteq coNP/poly. Treewidth parameterized by the deletion distance to a cluster graph has no polynomial kernel unless the AND-distillation conjecture does not hold. If time permits I will show which properties of treewidth were exploited in the reductions that yield these lower-bounds. | ||
| 21 October | Petteri Kaski | Fast zeta transforms for lattices with few irreducibles |
| Abstract We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with $v$ elements, $n$ of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size $O(vn)$ for computing the zeta transform and its inverse, thus enabling fast multiplication in the Möbius algebra. | ||
| 14 October | No Seminar | |
| 7 October | Michał Pilipczuk | Problems parameterized by treewidth tractable in single exponential time: a logical approach |
| Abstract We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL LOGIC (ECML), which captures a vast majority of problems known to be tractable in single exponential time when parameterized by treewidth. It appears that all these results can be subsumed by the theorem that model checking of ECML admits an algorithm with such complexity. We extend ECML by adding connectivity requirements and, using the Cut&Count technique, prove that problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigational character of the introduced logic is informally justified by a negative result that two expository problems involving non-acyclic conditions, C_l-VERTEX-DELETION and GIRTH>l-VERTEX-DELETION for l>=5, do not admit such a robust algorithm unless Exponential Time Hypothesis fails. | ||
| 30 September | Fedor Fomin | Linear kernels for dominating set on H-minor-free graphs |
| 23 September | Ramanujan Maadapuzhi Sridharan | A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments |
| Abstract In the {\sc $k$-Feedback Arc/Vertex Set} problem we are given a directed graph $D$ and a positive integer $k$ and the objective is to check whether it is possible to delete at most $k$ arcs/vertices from $D$ to make it acyclic. Dom et al.[{\em CIAC, 2006}\,] initiated a study of the {\sc Feedback Arc Set} problem on bipartite tournaments ({\sc $k$-FASBT}) in the realm of parameterized complexity. They showed that {\sc $k$-FASBT} can be solved in time $O(3.373^k n^6)$ on bipartite tournaments having $n$ vertices. However, until now there was no known polynomial sized problem kernel for {\sc $k$-FASBT}. In this paper we obtain a cubic vertex kernel for {\sc $k$-FASBT}. This completes the kernelization picture for the {\sc Feedback Arc/Vertex Set} problem on tournaments and bipartite tournaments. We obtain our kernel using a non-trivial application of ``independent modules'' which could be of independent interest. | ||
| Thursday 15 September (with lunch at 12 as usual) | Saket Saurabh | Surprise talk |
| 9 September | No seminar due to IPEC 2011 | |
| 2 September | No seminar due to WORKER 2011 | |
| 26 August, At 10.30!! | Daniel Lokshtanov | Outlier Detection for DNA Fragment Assembly |
Joint work with Christina Boucher and Christine Lo, UCSD Abstract A major impediment in the development of inexpensive, efficient, full genome sequencing is the large portion of erroneous reads produced by sequencing platforms. Error correction is the computational process that attempts to identify and correct these mistakes. Several classical stringology problems, including the Consensus String problem, are used to model error correction. However, a significant shortcoming of using these formulations is that they do not account for a few of the reads being too erroneous to correct; these outlier strings potentially have great effect on the solution, and should be detected and removed. We formalize the problem of error correction with outlier detection by defining the Consensus String with Outliers problem. Given a set S of n length-L strings, and parameters d and k, the objective in the Consensus String with Outliers problem is to find a subset S^* of S of size n-k and a string s such that \sum_{s_i \in S^*} d(s_i, s) <= d. Here d(x, y) denotes the Hamming distance between the two strings x and y. We prove the following results: - The variant of Consensus String with Outliers where the number k of outliers is fixed and the total distance \sum{s_i \in S^*} d(s_i, s) is to be minimized admits a simple PTAS. Our PTAS can easily be modified to also handle the variant of the problem where a hard upper bound d on the total distance is given as input, and the size of S^* is to be maximized. The approximation schemes are in fact so simple that our results are best viewed as a performance guarantee on natural heuristics for the problem when the parameters of the heuristic are chosen appropriately. - Under the natural assumption that the number of outliers k is small, the PTAS for the distance minimization version of Consensus String with Outliers performs very well. In particular, as long as k <= n/2 the algorithm provides a (1+e) approximate solution in time f(1/e)(nL)^{O(1)} and thus is an EPTAS. - In order to improve the PTAS for Consensus String with Outliers to an EPTAS, the assumption that k is small is necessary. Specifically, when k is allowed to be arbitrary the Consensus String with Outliers problem does not admit an EPTAS unless FPT=W[1]. - The decision version of {\em Consensus String with Outliers} is fixed parameter tractable when parameterized by d/(n-k). and thus, also when parameterized by just d. To the best of our knowledge, Consensus String with Outliers is the first problem that admits a PTAS, is fixed parameter tractable when parameterized by the value of the objective function, but which provably does not admit an EPTAS under plausible complexity assumptions. To accommodate for this our hardness of approximation proof needs to combine parameterized reductions and gap preserving reductions in a novel manner. | ||
| 19 August | André Nichterlein | On Tractable Cases of Target Set Selection |
Abstract We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size "target set" such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are activated. Then, a vertex becomes activated if the number of its activated neighbors exceeds its threshold, and so on. TSS models the spread of information and influence in networks. Complementing results on its approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters "diameter", "cluster editing number", "vertex cover number", and "feedback edge set number" of the underlying graph on the problem's computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter "size of the target set". TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter treewidth. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter cluster edge deletion number, yielding tractability for certain dense networks. | ||
Vårsemesteret 2011
This semester our algorithms seminar is on Fridays, as usual.
In charge of the seminars is Pim van 't Hof.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (library).
| 17 June | Reza Saei | Some Topics on Domination |
| 10 June | (Minicourse by Patrice Ossona de Mendez) | |
| 27 May | Serge Gaspers | Kernels for Global Constraints |
| 20 May | (Treewidth Workshop) | |
| 13 May | Petr Golovach | Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees |
| 29 April | Pim van 't Hof | Contracting Graphs to Paths and Trees |
| 22 April | (Easter Break) | |
| 15 April | Daniel Meister | Induced Subgraph Isomorphism on Two Classes of Perfect Graphs |
| 8 April | Erik Jan van Leeuwen | PTAS for Weighted Set Cover on Unit Squares |
| 1 April | Johannes Langguth | Sequential and Parallel Algorithms for Bipartite Matching |
| 25 March | Marek Cygan | The Stubborn Problem is Stubborn No More |
| 18 March | Yuri Rabinovich | On Complexity of the Sub-Pattern Problem |
| 11 March | Fredrik Manne | Efficient Self-Stabilizing Graph Searching in Trees |
| 4 March | Jan Arne Telle | Locally Constrained H-Homomorphism on Graphs of Logarithmic Boolean-Width |
| 25 February | (Winter School) | |
| 18 February | Sven Köhler | Fault-Containing Self-Stabilization in Asynchronous Systems with Constant Fault-Gap |
| 11 February | Dimitrios Thilikos | Deciding More Containment Relations in Embedded Graphs in FPT Time |
| 4 February | Bengt Aspvall | Utforske Matematikk fra IKT (Uten Bruk av Datamaskin) - Departmental seminar, 13:15-15:00, Lille Auditorium, SV-bygget |
| 28 January | Thomas Ågotnes | Normative State Transition Systems: Logic, Games and Complexity |
| 7 January | Bart Jansen | Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter |
2010
Høstsemesteret 2010
This semester our algorithms seminar is back on Fridays, as usual.
In charge of the seminars is Erik Jan van Leeuwen.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (library).
| 3 December | Jan Arne Telle | Social Networks |
| 26 November | Lisa Schreiber | The Unbounded Knapsack Problem and the Generalized Cordel Property |
| 19 November | Geevarghese Philip | t-Total Vertex/Edge Cover: Fixed Parameter Tractability and Kernelization Complexity |
| 5 November | Fran Rosamond | On the Complexity of Some Constraint Satisfaction Problems with Global Constraints and Convexity |
| 29 October | Danny Hermelin | Minimum Vertex Cover in Rectangle Graphs |
| 15 October | Binh-Minh Bui-Xuan | Recipe for computing generalisations of modular decomposition |
| 8 October | Neeldhara Misra | Connected Dominating Set and Short Cycles |
| 1 October | Mike Fellows | Why vote? |
| 24 September | Frederic Dorn | Fast Minor Testing in Planar Graphs |
| 17 September | Martin Vatshelle | Faster Algorithms on Branch and Clique Decompositions |
| 10 September | Saket Saurabh | Parameterized Problems that have Slightly Superexponential Time Algorithms |
| 3 September | Frank Kammer | Approximate Tree Decompositions of Planar Graphs in Linear Time |
| 27 August | Frank Kammer | Disjoint Paths on Chordal Graphs |
| 20 August | Daniel Lokshtanov | Clustering with Local Restrictions |
Vårsemesteret 2010
This semester we had to move our algorithms seminar to Thursdays instead of Fridays, since several members of the group have Norwegian course on Fridays.
In charge of the seminars is Binh-Minh Bui-Xuan.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (library).
| 17 June | Yahav Nussbaum | Maximum Flow in Directed Planar Graphs with Vertex Capacities |
| 10 June | Pinar Heggernes | Generalized graph clustering: recognizing (p,q)-cluster graphs |
| 3 June | Rémy Belmonte | On classes of graphs with logarithmic boolean-width |
| 27 May | Dieter Kratsch | Colorings with few colors |
| 6 May | Michel Habib | On the computation of 2-join |
| 29 April | Erik Jan van Leeuwen | Parameterized approximability: EPTAS and beyond |
| 8 April | Daniel Meister | About the existence of good digraph width measures |
| 25 March | Mostofa Patwary | Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure |
| 18 March | Petr Golovach | Cops and Robber Game Without Recharging |
| 11 March | Pierre Fraigniaud | Compact Ancestry Schemes and Small Universal Posets |
| 25 February | (Winter School) | |
| 18 February | Johannes Langguth | A parallel algorithm for bipartite matching |
| 11 February | Jesper Nederlof | Saving Space by Algebraization 2 |
| 4 February | Daniel Lokshtanov | Known Bounded Treewidth Algorithms are (Probably) Optimal |
| 28 January | Mamadou Kanté | Rank-width of edge-colored graphs |
| 21 January | Nicolas Bourgeois | Approximating with moderately exponential algorithms |
| 15 January | Frederic Dorn | A faster FPT-algorithm for Planar Subgraph Isomorphism |
2009
Høstsemesteret 2009
In charge of the seminars is Yngve Villanger.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (library).
| 11 December | Jean Blair | Discovering Open Graph Theoretic Problems Motivated by Network Science |
| 4 December | Johan van Rooij | Exact Algorithms for Edge Domination |
| 27 November | Pim van 't Hof | Computing Role Assignments of Chordal Graphs |
| 20 November | Daniel Lokshtanov | Saving Space By Algebraization |
| 6 November | Pinar Heggernes | Linear clique-width of some proper interval graphs |
| 30 October | Rodica Mihai | Edge search number of cographs in linear time |
| 23 October | 25th anniversary of Department of informatics | |
| 16 October | GROW 2009 | |
| 9 October | Michaël Rao | Last Cases of Dejean's Conjecture |
| 2 October | Fedor V. Fomin | Local Search: Is brute-force avoidable? |
| 25 September | Abhijin Adiga | Lower Bounds for Boxicity |
| 18 September | Jean Blair | An Efficient Self-stabilizing Distance-2 Coloring Algorithm |
| 4 September | Paul Bonsma | Finding fullerene patches in polynomial time |
| 28 August | Sourav Chakraborty | Market Equilibrium with Transaction Costs |
| 21 August | Yuri Rabinovich | On Cut Dimension of a Metric Space |
Vårsemesteret 2009
In charge of the seminars is Daniel Meister.
-- The seminar is in room 3137 at 12:45 unless otherwise specified.
-- We start with lunch at 12:00 (3137 or library).
| 19 June | Jesper Nederlof | Möbius inversion 2 |
| 12 June | Jesper Nederlof | Möbius inversion |
| 5 June | Daniel Meister | Chordal digraphs |
| 29 May | Mostofa Ali Patwary | A Scalable Parallel Union-Find Algorithm for Distributed Memory Computers |
| 22 May | Saket Saurabh | 3k-Vertex Kernel for Maximum Internal Spanning Tree |
| 15 May | Venkatesh Raman | Polynomial Kernel for Dominating Set on Graphs of Bounded Degeneracy |
| 8 May | Dieter Kratsch | Convex Recoloring Revisited |
| 24 April | Andrzej Proskurowski | Modeling computer/communication networks |
| 17 April | Daniel Lokshtanov | Hypergraph Max-Cut Meets Hypergraph Spanning Tree |
| 3 April | Holger Dell | Sparsification Lower Bounds |
| 27 March | Isolde Adler | The homomorphism problem for structures |
| 20 March | Binh-Minh Bui-Xuan | Need-For-Speed (on the track of an optimal rankwidth decomposition: pros and cons) |
| 6 March | Pınar Heggernes | A guided tour to İstanbul |
| 27 February | Saket Saurabh | Kernelization - A Current View Point |
| 20 February | Petr Golovach | Guarding games on graphs |
| 13 February | Morten Mjelde | PhD defence |
| 6 February | Daniel Lokshtanov | Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves |
| 30 January | Tınaz Ekim | Polar graphs |
| 23 January | Isolde Adler | Computing excluded minors |
| 16 January | Sang-il Oum | Maximum number of complete subgraphs in a certain graph |
| 9 January | Yngve Villanger | Faster parameterized algorithms for Minimum Fill-in |
2008
Høstsemesteret 2008
In charge of the seminars is Johannes Langguth.
-- The seminar is in room 2143 at 13:00 unless otherwise specified.
-- We start with lunch at 12:15 in the third floor (3137 or library).
| 12 December | Jesper Nederlof | Inclusion-exclusion for hard problems |
| 28 November | Ioan Todinca | |
| 21 November | Ruben van der Zwaan | Vertex ranking |
| 14 November | Haiko Müller | On a Disparity Between Relative Cliquewidth and Relative NLC-width |
| 7 November | Binh-Minh Bui-Xuan | On speeding up divide-and-conquer algorithms: making faster unifications or doing less conquests? |
| 31 October | Matthias Mnich | Computing a Maximum Agreement Supertree |
| 17 October | Federico Mancini | Clustering with partial information |
| 10 October | Jan Arne Telle | The Bergen Graph Parameter Project, a proposal for discussion |
| 3 October | Michal Walicki | Kernels of digraphs |
| 26 September | Daniel Lokshtanov | Graph Layout Problems Parameterized by Vertex Cover |
| 19 September | Michel Habib | Minimal separators and maximal cliques in chordal graphs revisited starts 11:00 in room 3137 |
| 12 September | Petr Golovach | A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs |
| 5 September | Serge Gaspers | Iterative Compression and Exact Algorithms |
| 22 August | Federico Mancini | Algorithms for search engines (prøveforelesing) starts 13:15 in room 2142 |
Vårsemesteret 2008
In charge of the seminars is Morten Mjelde.
-- The seminar is at room 3137 at 13.00.
| 8 February | Binh-Minh Bui-Xuan | Tree-representation of set families and graph decompositions |
| 15 February | Petr Golovach | Generalized domination in degenerate graphs: ambivalence and complexity |
| 22 February | Serge Gaspers | Cleaning and Protecting a Graph |
| 29 February | Morten Mjelde | Temporal Partition in Sensor Networks. |
| 7 March | Johannes Langguth | Market Equilibria |
| 14 March | Joanna Bauer | Dissertation |
| 28 March | Michael Fellows | Correlation Clustering, Graph Separation, and Removing Necklaces: A Tale of Equivalent Open Problems |
| 4 April | Mikko Koivisto | Exponential-time algorithms for Bayesian networks |
| 11 April | Daniel Lokshtanov | Cutwidth of split graphs, threshold graphs, and proper interval graphs |
| 18 April | Gregori Sorkin | Faster solving, counting, and sampling |
| 25 April | Saket Saurabh | Finding sub graphs whose matching number equals its minimum vertex cover number |
| 9 May | Petteri Kaski | Deletion--contraction invariants and fast subset convolution |
| 23 May | Marc Bezem | Shortest paths in hypergraphs |
| 30 May | Frederic Dorn | An FPT Algorithm for Directed Spanning k-leaf |
| 6 June | Yngve Villanger | Computing treewidth with a help of firefighters |
| 13 June | Jan Arne Telle | H-join graphs and rankwidth |
| 20 June | Lene Monrad Favrholdt | Comparing First-Fit and Next-Fit for Online Edge Coloring |
| 27 June | Sushmita Gupta | Feedback Art set problem in bipartite tournaments |
2007
Høstsemesteret 2007
In charge of the seminars is Daniel Lokshtanov.
-- Every Friday we have Algorithms seminar in Room 2143 at 12:30.
| 30 November | Petr Golovach | On tractability of Cops and Robbers game |
| 14 September | Frederic Dorn | Dissertation |
| 7 September | Fedor Fomin | Parameterized subexponential algorithms |
| 31 August | Yngve Villanger | Improved parameterized algorithms for feedback vertex set problem |
Vårsemesteret 2007
In charge of the seminars is Federico Mancini.
-- Every Friday we have Algorithms seminar in Room 2143 at 12:30.
-- Every Friday we have Algorithms lunch at the library on the 3rd floor at 11:45.
| 15 June | Feodor Dragan | Distance and Routing Labeling Schemes in Graphs with Applications |
| 8 June | R. Sritharan | 4-leaf powers: structure and recognition |
| 1 June | Yngve Villanger | k-interval completions |
| 1 June | Moritz Mueller | Parameterized Analogues of the Valiant- Vazirani Lemma |
| 25 May | Danny Hermelin | Lower bounds for kernelization |
| 18 May | Petr Golovach | Computational complexity of generalized domination for chordal graphs |
| 11 May | Qin Xin | Faster treasure hunts and better strongly universal exploration sequencestd> |
| 4 May | - | Research school |
| 27 April | Elena Losievskaja | Approximation algorithms for the Maximum Independent set problem in hypergr aphs |
| 20 April | Mike Fellows | Parameterization of complexity is all about structure theory, and how to use it |
| 13 April | Dimitrios M. Thilikos | Graph Searching in a Crime Wave |
| 30 March | Rodica Mihai | Mixed search number and linear-width of interval and split graphs |
| 23 March | Charis Papadopulos | Single-edge monotonic sequences of graphs |
| 16 March | Mathieu Liedloff | An exact algorithm for the minimum dominating clique problem |
| 9 March | Morten Mjelde | Self-stabilizing matching |
| 2 March |