Algorithms seminar series
Seminaret bygger på INF234, 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.
2017
Autumn 2017
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 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.
28. 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 | -------- | Winter holidays break |
23 February | Alexey Stepanov | Counting Dominating Sets |
16 February | Fedor Fomin | On Self Duality of Pathwidth in Polyhedral Graph Embeddings |
9 February | Fredrik Manne | New Star and Acyclic Coloring Algorithms |
2 February | Saket Saurabh | Parameterized complexity of Directed Max Leaf |
26 January | Yngve Villanger | Characterizing minimal interval completions |
2006
Høstsemesteret 2006
In charge of the seminars is Serge Gaspers.
-- On announced Fridays we have Algorithms seminar in Room 2142 at 12:30.
-- Every Friday (regardless of whether there is a seminar afterwards)
we have Algorithms lunch at the HIB cafeteria at 11:45
(everybody is welcome to join).
15 December | Qin Xin | Faster Centralized Communication in Radio Networks |
8 December | Daniel Meister | Computing treewidth and minimum fill-in for permutation graphs in linear time |
1 December | Serge Gaspers | Branching and Treewidth Based Exact Algorithms |
24 November | Omid Amini | Minimal Selectors and Fault Tolerant Networks |
17 November | Jan Arne Telle | On the crossing number of graphs with an excluded minor |
10 November | Prudence Wong | Energy Efficient Online Deadline Scheduling |
3 November | Morten Mjelde | A Memory Efficient Self-stabilizing Algorithm for Maximal k-packing |
27 October | Charis Papadopoulos | Making arbitrary graphs transitively orientable: Minimal comparability completions |
20 October | Daniel Lokshtanov | Determining treelength is hard (Treelength has been introduced in this paper) |
6 October | Parameterized Complexity of Dominating Set | |
29 September | Gregory Gutin | Parameterized Complexity for Graph Linear Arrangement Problems (abstract) |
22 September | Federico Mancini | A completely dynamic algorithm for split graphs |
8 September | Magnus Wahlström | Approaches to a #2SAT algorithm analysis |
1 September | Frederic Dorn | Dynamic Programming and Fast Matrix Multiplication |
28 August | Sbastien Tixeuil | Self-stabilization |
Vårsemesteret 2006
In charge of the seminars is Frederic Dorn.
-- On announced Fridays we have Algorithms seminar in Room 2143 at
12:30.
-- Every Friday (regardless of whether there is a seminar afterwards)
we have Algorithms lunch at the HIB cafeteria at 11:45
(everybody is welcome to join).
2 June | Qin Xin | Optimal Gossiping with Unit Size Messages in Known Topology Radio Networks |
19 May | Christophe Paul | Algorithmic aspects of modular decomposition |
5 May | Herman Ruge Jervell | Wellordering finite trees (abstract) |
28 April | Hans Bodlaender | On Exact Algorithms for Treewidth |
31 March | Dieter Kratsch | Lower Bounds for Exact Maximum Independent Set Algorithms |
24 March | Artem Pyatkin | On polynomial algorithms on the vector sum problem |
17 March | Ioan Todinca | Proper interval graphs: a minimal completion algorithm (abstract) |
10 March | Federico Mancini | Minimal Split Completions of Graphs |
3 March | Frederic Dorn | Two birds with one stone: the best of branchwidth and treewidth with one algorithm |
24 February | Yngve Villanger | Improved Exponential-time Algorithms for Treewidth and Minimum Fill-in |
17 February | Saket Saurabh | Parameterized algorithms for finding feedback vertex set |
10 February | Eva-Marta Lundell | Subexponential-time framework for optimal embeddings of graphs in integer lattices |
3 February | Jan Kratochvil | Distance constrained graph labeling and graph homomorphisms |
27 January | Fredrik Manne | Parallel graph coloring for distributed memory computers |
20 January | Serge Gaspers | Exponential algorithms for the Maximum P_3-free Induced Subgraph Problem |
13 January | Fabrizio Grandoni | Exponential time algorithm for Independent Set: Measure & Conquer |
2005
Høstsemesteret 2005
In charge of the seminars is Alexey (Ljosha) Stepanov.
-- On announced Fridays we have Algorithms seminar in Grupperom 2101 at
12:30.
-- Every Friday (regardless of whether there is a seminar afterwards)
we have Algorithms lunch at the HIB cafeteria at 11:45
(everybody is welcome to join).
18 November | Qin Xin | Faster Communication in Ad-hoc Radio Networks(abstract) |
11 November | Jan Arne Telle | New results on branchwidth of graphs |
4 November | Alexey Stepanov | Bounding the Number of Minimal Dominating Sets: a Measure and Conquer Approach |
14 October | Karol Suchan | Minimal interval completions |
7 October | Charis Papadopoulos | Drawing graphs using modular decomposition |
30 September | Frederic Dorn | Subexponential Algorithms for Planar Hamiltonicity |
23 September | Daniel Paulusma | Backbone coloring |
16 September | Fedor Fomin | On pathwidth of 3-regular graphs |
9 September | Jiri Fiala | Degree structure of a graph and degree matrices (abstract) |
2 September | Pinar Heggernes | Exact algorithms for graph homomorphisms |
Vårsemesteret 2005
In charge of the seminars is Alexey (Ljosha) Stepanov.
-- On announced Fridays we have Algorithms seminar in Grupperom 2104 at
12:30.
-- Every Friday (regardless of whether there is a seminar afterwards)
we have Algorithms lunch at the HIB cafeteria at 11:45
(everybody is welcome to join).
10 June | Daniel Lokshtanov | Optimal broadcast domination of arbitrary graphs in polynomial time |
22 April | Artem Pyatkin | On maximum number of minimal dominating sets in graphs |
15 April | Dimitrios Thilikos | Faster fixed-parameter tractable algorithms for matching and packing problems (abstract) |
8 April | Marina Lipshteyn | Representations of Edge Intersection Graphs of Paths in a Tree (abstract) |
11 March | Dieter Kratsch | The use of modular decomposition to design linear time algorithms for (P_5,gem)-free graphs (abstract) |
4 March | Pierre Fraigniaud | A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decompositions |
4 February | Alexey Stepanov | Quasiconvex Analysis of Backtracking Algorithms |
28 January | Di Yuan | Optimization of Pilot Signal Power in WCDMA Networks |
2004
Høstsemesteret 2004
In charge of the seminars is Frederic Dorn.
Fridays 12:30 (etter algoritmelunsj
11:45 i HIB kantinen) Grupperom 2103.
17 Deceember | Elias Dahlhaus | Converting a nested dissection algorithm into a minimal elimination algorithm |
10 December | Yngve Villanger | Computing minimal triangulations in time O(n log n) = o(n2.376) |
3 December | Joanna Bauer | Minimizing the energy for broadcasting in wireless networks |
12 November | Frederic Dorn | Comparing tree decompositions with branch decompositions |
29 October | Artem Pyatkin | On (k,l)-coloring of incidentors |
15 October | Anne Berry | Recognizing probe chordal graphs |
Vårsemesteret 2004
In charge of the seminars is Fedor Fomin.
Fridays 12:30 (etter algoritmelunsj
11:45 i HIB kantinen) Grupperom 2104.
7 May | Jan Kristian Haugland | Regulare induserte undergrafer av gittere uten korte sykeler |
30 April | Fredrik Manne | Efficient multi-stage self-stabilizing algorithms on tree networks |
22 April | Ioan Todinca | Computing the treewidth for graphs with "few" minimal separators |
18 March | Fedor Fomin | Exact algorithms for treewidth |
11 March | Fedor Fomin | A Simple and Fast Approach for Solving Problems on Planar Graphs |
20 February | Dag Haugland | A tree decomposition approach to MI-FAP |
13 February | Bjørge Solli | David Eppstein's paper on Small Maximal Independent Sets and Faster Exact Graph Coloring |
13 February | Finse Winterschool Feedback | |
30 January | Elena Prieto | Method of coordinatized kernels on the bipartite subgraph problem |
2003
Høstsemesteret 2003
In charge of the seminars is Fedor Fomin.
Fridays 12:30 (etter algoritmelunsj
11:45 i HIB kantinen) Grupperom 2104.
11 Decem)er | Dimitrios M. Thilikos | On the Monotonicity of Games Generated by Symmetric Submodular Functions |
7 November | Yngve Villanger | A vertex incremental approach to maintaining chordal graphs dynamically II |
31 October | Pierre Fraigniaud | Distributed Hash Tables for P2P Network |
30 October | Dieter Kratsch | Certifiying Algorithms |
24 October | Pinar Heggernes | The minimum degree heuristic and the minimal triangulation process |
17 October | Christian Sloper | New techniques in designing FPT-algorithms |
10 October | Christian Sloper | Using Vertex Cover Structure in designing FPT-algorithms - the case of k-Internal Spanning Tree |
3 October | Yngve Villanger | A vertex incremental approach to maintaining chordal graphs dynamically |
26 September | Jan Arne Telle | Catval graphs and the catwidth graph parameter |
5 September | Fedor Fomin | Fixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs |
29 August | Jan Arne Telle | Graph searching, elimination trees, and a generalization of bandwidth |
Vårsemesteret 2003
In charge of the seminars is Fedor Fomin.
Hovedtema for semesteret er Exact algorithms for NP-hard problems
Fridays 12:15 Grupperom 2143.
15 May 2003 | Christian Schindelhauer | Worst Case Mobility in Ad Hoc Networks |
2 May 2003 | Fedor Fomin | Exact algorithms for NP-hard problems VII |
25 April 2003 | Pinar Heggernes | Broadcast domination for interval graphs and trees |
11 April 2003 | Fedor Fomin | Exact algorithms for NP-hard problems VI |
28 March 2003 | Hans Bodlaender | Treewidth k in linear time |
27 March 2003 | Hans Bodlaender | Treewidth: Heuristics and Preprocessing |
21 March 2003 | Fedor Fomin | Exact algorithms for NP-hard problems V |
14 March 2003 | Fedor Fomin | Exact algorithms for NP-hard problems IV |
28 February 2003 | Fedor Fomin | Exact algorithms for NP-hard problems III |
18 February 2003 | Frederic Dorn | LEDA & Tuning Algorithms for Hard Planar Graph Problems |
7 February 2003 | Fedor Fomin | Exact algorithms for NP-hard problems II |
24 January 2003 | Fedor Fomin | Exact algorithms for NP-hard problems |
2002
Høstsemesteret 2002
In charge of the seminars is Fredrik Manne.
Fridays 12:15 Grupperom 2101.
29 November 2002 | Jan Arne Telle | Planar graphs and treewidth II |
22 November 2002 | Jan Arne Telle | Planar graphs and treewidth I |
8 November 2002 | Fredrik Manne | A Linear time 2-approximation algorithm for maximum weighted matching in general graphs |
25 October 2002 | Leda-gruppen | Introduksjon til Leda |
18 October 2002 | Pinar Heggernes | Maximum Cardinality Search for Minimal Triangulations |
4 October 2002 | Kjell Jørgen Hole | Algorithmic problems in mobile and ad-hoc networks |
27 September 2002 | Assefaw H. Gebremedhin | Parallel Distance-k Coloring Algorithms for Numerical Optimization |
13 September 2002 | Yngve Villanger | Efficient Implementation of a Minimal Triangulation Algorithm |
Vårsemesteret 2002
In charge of the seminars is Jean Blair.
Fridays 12:15 Grupperom 2101.
8 February 2002 | Jan Kratochvil | Intersection graphs |
15 February 2002 | Jiri Fiala | The independence and coloring problems on disk graphs |
22 February 2002 | Ondra Pangrac | String graphs |
1 March 2002 | Jean Blair | Winter school impressions - AAR |
8 March 2002 | Petter Kristiansen | A self-stabilizing algorithm for maximal 2-packing |
15 March 2002 | Jan Arne Telle | Tree decompostions of small pathwith |
22 March 2002 | Jan Arne Telle | Tree decompostions of small pathwith (continued) |
5 April 2002 | Petter Kristiansen | Domination, independence, irredundance |
12 April 2002 | Jean Blair | Generalized vertex covers |
19 April 2002 | group work | Classes of graphs having vertex covers that are: K-partite, independent, c lique, or acyclic |
26 April 2002 | group work | Graphs with induced path and induced tree vertex covers |
3 May 2002 | group work | More on induced path and induced-tree vertex covers |
14 May 2002 | Fedor Fomin | Radio networks and graph colorings |
2001
Høstsemesteret 2001
Dette semesteret har vi ikke algoritmeseminar siden det nye kurset
I238 g�r for f�rste gang med tema som er nye for de fleste.
Interesserte er velkommen til � delta
i deler av kurset.
Vårsemesteret 2001
Dette semesteret har vi ikke algoritmeseminar siden vi gjennomg�r
utvalgte tema i algoritmer i I239. Interesserte er velkommen til
� f�lge med p� ulike deler av kurset.
2000
Høstsemesteret 2000
Fredager 12:15 Grupperom 2103.
Hovedtema for semesteret er FPT - Fixed Parameter Tractability
Ansvarlig: Jan Arne Telle
8 September 2000 | Jan Arne Telle | Fixed parameter tractability (FPT) | |
15 September 2000 | Christian Sloper | FPT : Bounded search trees | |
22 September 2000 | Petter Kristiansen | FPT : Reduction to a problem kernel | |
29 September 2000 | Petter Kristiansen | FPT : List of interesting problems | |
6 Oktober 2000 | Christian Sloper | FPT: Planar red blue dominating set | |
20 Oktober 2000 | Petter Kristiansen | FPT : Graph modification problem | |
27 Oktober 2000 | Fredrik Manne | NM i programmering 2000 | |
3 November 2000 | Pinar Heggernes | FPT : Minimum fill is FPT | |
10 November 2000 | Christian Sloper | FPT: Method of test sets | |
17 November 2000 | Jan Arne Telle | Deterministic finite tree automata | |
24 November 2000 | Petter Kristiansen | Method of test sets for regular tree languages | |
1 Desember 2000 | Jan Arne Telle | Bounded degree parsing trees | |
8 Desember 2000 | Petter Kristiansen | Method of test sets on graphs with bounded treewidth |
1999
Vårsemesteret 1999
Tema for semesteret: Grafalgoritmer for å minimere fyll
Ansvarlig: Pinar Heggernes
29/1 Magnus Halldorsson | Multicoloring of graphs |
5/2 Assefaw Hadish Gebremedhin | Parallell Graph Coloring |
12/2 Pinar Heggernes | Fyll: Hvorfor glissne matriser? |
19/2 Pinar | Fyll: Eliminasjonsordninger og fyll |
26/2 Jan Arne | Fyll: Kordale grafer I |
5/3 Jan Arne | Fyll: Kordale grafer II |
12/3 Jan Arne | Fyll: Kordale grafer III |
19/3 Utsatt | |
26/3 Petter Kristiansen | Pakking av grafer |
2/4 Påske | |
9/4 Fredrik Manne | Fyll: Min Degree og Nested Dissection |
16/4 Pinar Heggernes | Algoritmer for minimalt fyll |
23/4 Ole-Martin Kvinge | Grafalgoritmer for glisne matriser |
30/4 Anne Berry, Univ Montpellier, Frankrike | Algorithms for minimal fill |
7/5 Jan Kratochvil, Charles Univ, Prag, Tsjekkia | Partial covers of graphs |
14/5 Jiri Fiala, Charles Univ, Prag, Tsjekkia | Channel assignment problem |
21/5 Fredrik | Mer om fyll |
28/5 Knut Erstad | Visualisering ved hjelp av L-systemer |
31/5 Sidsel Horvei | Algoritmer for s�kemaskiner p� WWW |
1998
Høstsemesteret 1998
Ansvarlig: Jan Arne Telle
11/9 Jan Arne Telle | Mod-2 Independence and domination in graphs |
18/9 Alex Pothen, Old Dominion Univ., USA | Graph Reductions: a theory of incomplete factorization |
25/9 Magnus Halldorsson, | Channel Assignment in Radio Networks (Partitioning Planar Graphs into Strong Stable Sets) |
2/10 Elias Dahlhaus, Univ. Ko"ln, Tyskland | Minimal elimination orderings of chordal graphs |
9/10 Andrzej Proskurowski, Univ. of Oregon, USA | Multisource shortest path problems |
16/10 Sven Sigurdsson, Science Institute, University of Iceland | Elimination trees in parameter estimation problems. |
23/10 Bengt Aspvall | Approximations for the general block distribution of a matrix |
30/10 Fredrik Manne, UiB | Strukturert Data Partisjonering |
20/11 Yngve Lamo, UiB, | Developing algorithms by calculation. (Topological Sorting: an example using relational calculus) |
4/12 Dieter Kratsch, Univ Jena, Tyskland | |
11/12 Pinar Heggernes | Partitioning a set of functions into correlated subsets |
Planar Contraction