Seminar

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.

2014

 

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.

16. May TBA 
9. May TBA 
2. May TBA 
25. April TBA 
18. April Easter 
11. April Marcin Pilipczuk Online and dynamic algorithms for the Steiner tree problem.
4. AprilM S RamanujanParameterized Algorithms to Preserve Connectivity.
28. MarchSadia SharminGraph Partitioning
21. MarchWinter school 
14. March

Fernando S Villaamil

Computing Treedepth

7. MarchErik Jan van Leeuwen

Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs

28. FebruaryPål Grønås DrangeSubexponential Parameterized Complexity of Completion Problems
21. February

Peter Bro Miltersen

Real algebraic geometry in computational game theory - a consumer's perspective

14. FebruarySigve H SætherDomination Set parameterised by Clique-width
7. FebruaryReza SaeiFinding Disjoint Paths in Split Graphs
31. January

Ariel Gabizon

The r-simple k-path problem
24. JanuaryPinar HeggernesEnumeration in Graph Classes
17. JanuaryMichał PilipczukMinimum Bisection is FPT
10. JanuaryManu BasavarajuPartially Polynomial Kernels for SetCover and TestCover

 

2013

 

Høstsemesteret 2013

Reza Saei was in charge of the seminars for this semester.

 

13 DecemberGeevarghese PhilipPoint Line Cover: The Easy Kernel is Essentially Tight
6 DecemberIoan TodincaLarge Induced Subgraphs Via Triangulations and CMSO
29 NovemberChristophe PaulExplicit Linear Kernels via Dynamic Programming
22 NovemberMichał PilipczukPhD defense at 14:00 in room 2144
15 NovemberJan Arne TelleThe graph formulation of the union-closed conjecture
8 NovemberArchontia Giannopoulou  Polynomial Kernel for Tree Deletion Set
1 NovemberRémy BelmontePhD defense at 10:15 in room 2144
25 OctoberMartin VatsheleIndependent Set in Outerstring Graphs
18 OctoberIvan BliznetsLargest chordal and interval subgraphs faster than 2^n
11 OctoberPranabendu Misra
Faster Exact Algorithms for Some Terminal Set Problems
4 OctoberØyvind Ytrehus Coding theory and graphs
27 SeptemberDaniel LokshtanovIndependent Set in P5-Free Graphs in Polynomial Time
20 SeptemberBart JansenOn Sparsification for Computing Treewidth
13 SeptemberMateus de Oliveira OliveiraSubgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs
06 SeptemberMarcin PilipczukFast branching algorithm for Cluster Vertex Deletion

30 August

Jan Arne TelleUpper bounds on boolean-width with applications to exact algorithms
23 AugustFelix ReidlGraph classes of bounded expansion
16AugustPim Van 't HofThe price of connectivity for feedback vertex set

 

 

Vårsemesteret 2013

Thanks to Sigve Hortemo Sæther, for being in charge of the seminars for Spring semester.  

14 JuneMichał PilipczukA polynomial kernel for Planar Steiner Tree parameterized by the size of the tree
7 JuneDániel MarxCSPs and fixed-parameter tractability
31 MayFredrik ManneEfficient Sequential and Multicore Weighted Matching Algorithms
24 MayOndřej SuchýOn Explaining Integer Vectors by Few Homogenous Segments
17 MayNorwegian Constitution Day
10 MayMamadou KantéOn the linear rank-width and linear clique-width of Trees
3 MaySadia SharminEfficient Counting of Maximal Independent Sets in Sparse Graphs
26 AprilArvid LundervoldThe role of graph theory and network analysis in quantitative neuroimaging
19 AprilEmilio CoppaFrom asymptotics to performance profiling (and back)
12 April< No seminar >
5 AprilM. S. RamanujanBackdoors to Satisfiability via q-horn formulas
29 MarchEaster holiday
22 MarchJean-François CouturierA tight bound on the number of minimal dominating sets in split graph
15 MarchDimitrios M. ThilikosPolynomial gap extensions of the Erdős-Pósa theorem
8 MarchHenning FernauA multivariate analysis of pattern language problems
1 MarchDaniel MeisterRecent developments in clique-width computation
22 FebruaryWinter School 2013
15 FebruaryRémy BelmonteGraph rewriting
8 FebruaryYixin CaoInterval Deletion is Fixed-Parameter Tractable
1 FebruaryRémy BelmonteInduced Immersions
25 JanuarySven SimonsenThe complexity of finding arc-disjoint spanning trees and branchings in digraphs. FPT approach.
18 JanuaryDaniel LokshtanovNear-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 DecemberArchontia GiannopoulouLifo-search on (Di)graphs
7 DecemberPinar HeggernesThe maximum number of feedback vertex sets in chordal graphs and cographs
5 December*Hans BodlaenderConnectivity problems on graphs of small treewidth
30 NovemberHans BodlaenderPreprocessing and kernelization for Treewidth and Pathwidth
23 NovemberFedor V FominSubexponential Parametrized Algorithm for Cluster Editing
16 NovemberReza SaeidinvarRamsey Numbers for Line Graphs and Perfect Graphs
9 NovemberErik Jan van LeeuwenParameterized Complexity of Induced H-Matching on Claw-Free Graphs
2 NovemberJanne KorhonenCounting in Halves and Fast Monotone Summation over Disjoint Sets
26 OctoberPim van 't HofOn the parameterized complexity of finding separators with non-hereditary properties
19 OctoberIvan BliznetsA new algorithm for parametrized MAX-SAT
12 OctoberDaniel LokshtanovPolynomial Kernel for Planar F-Deletions
5 OctoberIgnasi SauParameterized domination in circle graphs
28 SeptemberMichał PilipczukRandomized contractions
21 SeptemberYngve VillangerSearching for better fill-in
14 SeptemberMartin VatshelleThe Point-Set Embeddability Problem for Plane Graphs
7 SeptemberFrederic DornShort-term hydro scheduling from the algorithmic perspective
3 September*Bruce ReedCatching a Drunk Miscreant
31 AugustHenning FernauSaving on Phases: Parameterized Approximation for Total Vertex Cover
24 AugustRajesh ChitnisDirected Multiway Cut is FPT
17 AugustJan Arne TelleFPT 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 MayPeter GolovachInduced Disjoint Paths in AT-free Graphs
8 JuneMartin VatshelleLower bounds on treewidth for practical computing (trial lecture)
1 June Mini-school on Width-Minors-Matroids
25 MayArash RafieyOrdering without bad patterns
11 MayRémy BelmonteOpen problems session
27 AprilMichał PilipczukOn group feedback vertex set parameterized by the size of the cutset

30 March

Igor SemaevFrom Jacob Bernoulli to Modern Cryptography
23 MarchBengt AspvallSorting Algorithms As Special Cases Of A Priority Queue Sort
16 MarchPim van 't HofObtaining a Bipartite Graph by Contracting Few Edges
9 MarchArash RafieyHomomorphism Problem and Approximation
2 MarchMichał PilipczukOpen problems session
24 FebruaryFinse

10th Annual Winter School in Algorithms, Graph Theory, and Combinatorics

17 FebruaryPål Grønås DrangeA randomized polynomial kernel for Odd Cycle Transversal
10 FebruarySigve H. SætherBroadcast domination on block graphs
3 FebruaryMartin MilanicOn the (in-)approximability and exact algorithms for vector domination and related problems in graphs
20 JanuaryJean-Francois CouturierMaximum number of minimal dominating sets in graph classes
13 JanuaryErik Jan van LeeuwenAlgorithms for firefighting
6 JanuaryDaniel LokshtanovFaster 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 DecemberRémy BelmonteFinding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
9 December, 10.15, Large Auditorium!!Jesper NederlofSpace and Time Efficient Structural Improvements of Dynamic Programming Algorithms (PhD dissertation)
2 DecemberMichał PilipczukSolving 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 NederlofProperty testing (Trial lecture)
18 NovemberHenning FernauParameterized 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 NovemberDaniel PaulusmaLift 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 NovemberRuben van der ZwaanPreemptive 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 OctoberBart JansenPreprocessing 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 OctoberPetteri KaskiFast 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 OctoberNo Seminar
7 OctoberMichał 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 SeptemberFedor FominLinear kernels for dominating set on H-minor-free graphs
23 SeptemberRamanujan Maadapuzhi SridharanA 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 SaurabhSurprise 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 AugustAndré 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 JuneReza SaeiSome Topics on Domination
10 June (Minicourse by Patrice Ossona de Mendez)
27 MaySerge GaspersKernels for Global Constraints
20 May (Treewidth Workshop)
13 MayPetr GolovachComputing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
29 AprilPim van 't HofContracting Graphs to Paths and Trees 
22 April (Easter Break)
15 AprilDaniel MeisterInduced Subgraph Isomorphism on Two Classes of Perfect Graphs
8 AprilErik Jan van Leeuwen 

PTAS for Weighted Set Cover on Unit Squares

1 AprilJohannes LangguthSequential and Parallel Algorithms for Bipartite Matching
25 MarchMarek CyganThe Stubborn Problem is Stubborn No More
18 MarchYuri RabinovichOn Complexity of the Sub-Pattern Problem
11 MarchFredrik ManneEfficient Self-Stabilizing Graph Searching in Trees
4 MarchJan Arne TelleLocally Constrained H-Homomorphism on Graphs of Logarithmic Boolean-Width
25 February    (Winter School)
18 FebruarySven KöhlerFault-Containing Self-Stabilization in Asynchronous Systems with Constant Fault-Gap
11 FebruaryDimitrios ThilikosDeciding More Containment Relations in Embedded Graphs in FPT Time
4 FebruaryBengt AspvallUtforske Matematikk fra IKT (Uten Bruk av Datamaskin) - Departmental seminar, 13:15-15:00, Lille Auditorium, SV-bygget 
28 JanuaryThomas ÅgotnesNormative State Transition Systems: Logic, Games and Complexity
7 JanuaryBart JansenVertex 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 DecemberJan Arne TelleSocial Networks
26 NovemberLisa SchreiberThe Unbounded Knapsack Problem and the Generalized Cordel Property
19 NovemberGeevarghese Philipt-Total Vertex/Edge Cover: Fixed Parameter Tractability and Kernelization Complexity
5 NovemberFran RosamondOn the Complexity of Some Constraint Satisfaction Problems with Global Constraints and Convexity
29 OctoberDanny HermelinMinimum Vertex Cover in Rectangle Graphs
15 OctoberBinh-Minh Bui-XuanRecipe for computing generalisations of modular decomposition
8 OctoberNeeldhara MisraConnected Dominating Set and Short Cycles
1 OctoberMike FellowsWhy vote?
24 SeptemberFrederic DornFast Minor Testing in Planar Graphs
17 SeptemberMartin VatshelleFaster Algorithms on Branch and Clique Decompositions
10 SeptemberSaket SaurabhParameterized Problems that have Slightly Superexponential Time Algorithms
3 SeptemberFrank KammerApproximate Tree Decompositions of Planar Graphs in Linear Time
27 AugustFrank KammerDisjoint Paths on Chordal Graphs
20 AugustDaniel LokshtanovClustering 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 JuneYahav NussbaumMaximum Flow in Directed Planar Graphs with Vertex Capacities
10 JunePinar HeggernesGeneralized graph clustering: recognizing (p,q)-cluster graphs
3 JuneRémy BelmonteOn classes of graphs with logarithmic boolean-width
27 MayDieter KratschColorings with few colors
6 MayMichel HabibOn the computation of 2-join
29 AprilErik Jan van LeeuwenParameterized approximability: EPTAS and beyond
8 AprilDaniel MeisterAbout the existence of good digraph width measures
25 MarchMostofa PatwaryExperiments on Union-Find Algorithms for the Disjoint-Set Data Structure
18 MarchPetr GolovachCops and Robber Game Without Recharging
11 MarchPierre FraigniaudCompact Ancestry Schemes and Small Universal Posets
25 February(Winter School) 
18 FebruaryJohannes LangguthA parallel algorithm for bipartite matching
11 FebruaryJesper NederlofSaving Space by Algebraization 2
4 FebruaryDaniel LokshtanovKnown Bounded Treewidth Algorithms are (Probably) Optimal
28 JanuaryMamadou KantéRank-width of edge-colored graphs
21 JanuaryNicolas BourgeoisApproximating with moderately exponential algorithms
15 JanuaryFrederic DornA 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 DecemberJean Blair
Discovering Open Graph Theoretic Problems Motivated by Network Science
4 DecemberJohan van RooijExact Algorithms for Edge Domination
27 NovemberPim van 't HofComputing Role Assignments of Chordal Graphs
20 NovemberDaniel LokshtanovSaving Space By Algebraization
6 NovemberPinar HeggernesLinear clique-width of some proper interval graphs
30 October Rodica MihaiEdge search number of cographs in linear time
23 October 25th anniversary of Department of informatics
16 October GROW 2009
9 OctoberMichaël RaoLast Cases of Dejean's Conjecture
2 OctoberFedor V. FominLocal Search: Is brute-force avoidable?
25 SeptemberAbhijin AdigaLower Bounds for Boxicity
18 SeptemberJean BlairAn Efficient Self-stabilizing Distance-2 Coloring Algorithm
4 SeptemberPaul BonsmaFinding fullerene patches in polynomial time
28 AugustSourav ChakrabortyMarket Equilibrium with Transaction Costs
21
August
Yuri RabinovichOn 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 NederlofMöbius inversion 2
12
June
Jesper NederlofMöbius inversion
5
June
Daniel MeisterChordal digraphs
29
May
Mostofa Ali PatwaryA Scalable Parallel Union-Find Algorithm for Distributed Memory Computers
22
May
Saket Saurabh3k-Vertex Kernel for Maximum Internal Spanning Tree
15
May
Venkatesh RamanPolynomial Kernel for Dominating Set on Graphs of Bounded Degeneracy
8
May
Dieter KratschConvex Recoloring Revisited
24
April
Andrzej ProskurowskiModeling computer/communication networks
17
April
Daniel LokshtanovHypergraph Max-Cut Meets Hypergraph Spanning Tree
3
April
Holger DellSparsification Lower Bounds
27
March
Isolde AdlerThe homomorphism problem for structures
20
March
Binh-Minh Bui-XuanNeed-For-Speed (on the track of an optimal rankwidth decomposition: pros and cons)
6
March
Pınar HeggernesA guided tour to İstanbul
27
February
Saket SaurabhKernelization - A Current View Point
20
February
Petr GolovachGuarding games on graphs
13
February
Morten MjeldePhD defence
6
February
Daniel LokshtanovKernel(s) for Problems With no Kernel:  On Out-Trees With Many Leaves
30
January
Tınaz EkimPolar graphs
23
January
Isolde AdlerComputing excluded minors
16
January
Sang-il OumMaximum number of complete subgraphs in a certain graph
9
January
Yngve VillangerFaster 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 DecemberJesper NederlofInclusion-exclusion for hard problems
28 NovemberIoan Todinca 
21 NovemberRuben van der ZwaanVertex ranking
14 NovemberHaiko MüllerOn a Disparity Between Relative Cliquewidth and Relative NLC-width
7 NovemberBinh-Minh Bui-XuanOn speeding up divide-and-conquer algorithms: making faster unifications or
 doing less conquests?
31 OctoberMatthias MnichComputing a Maximum Agreement Supertree
17 OctoberFederico ManciniClustering with partial information
10 OctoberJan Arne TelleThe Bergen Graph Parameter Project, a proposal for discussion
3 OctoberMichal WalickiKernels of digraphs
26 SeptemberDaniel LokshtanovGraph Layout Problems Parameterized by Vertex Cover
19 SeptemberMichel HabibMinimal separators and maximal cliques in chordal graphs revisited

starts 11:00 in room 3137
12 SeptemberPetr GolovachA PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
5 SeptemberSerge GaspersIterative Compression and Exact Algorithms
22 AugustFederico ManciniAlgorithms 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 FebruaryBinh-Minh Bui-XuanTree-representation of set families and graph decompositions
15 FebruaryPetr GolovachGeneralized domination in degenerate graphs: ambivalence and complexity
22 FebruarySerge GaspersCleaning and Protecting a Graph
29 FebruaryMorten MjeldeTemporal Partition in Sensor Networks.
7 MarchJohannes LangguthMarket Equilibria
14 MarchJoanna BauerDissertation
28 MarchMichael FellowsCorrelation Clustering, Graph Separation, and Removing Necklaces: A Tale of Equivalent Open Problems
4 AprilMikko KoivistoExponential-time algorithms for Bayesian networks
11 AprilDaniel LokshtanovCutwidth of split graphs, threshold graphs, and proper interval graphs
18 AprilGregori SorkinFaster solving, counting, and sampling
25 AprilSaket SaurabhFinding sub graphs whose matching number equals its minimum vertex cover number
9 MayPetteri KaskiDeletion--contraction invariants and fast subset convolution
23 MayMarc BezemShortest paths in hypergraphs
30 MayFrederic DornAn FPT Algorithm for Directed Spanning k-leaf
6 JuneYngve VillangerComputing treewidth with a help of firefighters
13 JuneJan Arne TelleH-join graphs and rankwidth
20 JuneLene Monrad FavrholdtComparing First-Fit and Next-Fit for Online Edge Coloring
27 JuneSushmita GuptaFeedback 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 NovemberPetr GolovachOn tractability of Cops and Robbers game
14 SeptemberFrederic DornDissertation
7 SeptemberFedor FominParameterized subexponential algorithms 
31 AugustYngve VillangerImproved 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 JuneFeodor DraganDistance and Routing Labeling Schemes in Graphs with Applications
8 JuneR. Sritharan4-leaf powers: structure and recognition
1 JuneYngve Villangerk-interval completions
1 JuneMoritz MuellerParameterized Analogues of the Valiant-
Vazirani Lemma
25 MayDanny HermelinLower bounds for kernelization
18 MayPetr GolovachComputational complexity of generalized domination for chordal graphs
11 MayQin XinFaster treasure hunts and better strongly universal exploration sequencestd>
4 May-Research school
27 AprilElena LosievskajaApproximation algorithms for the Maximum Independent set problem in hypergr
aphs
20 AprilMike FellowsParameterization of complexity is all about structure theory, and how
to use it
13 AprilDimitrios M. ThilikosGraph Searching in a Crime Wave
30 MarchRodica MihaiMixed search number and linear-width of interval and split graphs
23 MarchCharis PapadopulosSingle-edge monotonic sequences of graphs
16 MarchMathieu LiedloffAn exact algorithm for the minimum dominating clique problem
9 MarchMorten MjeldeSelf-stabilizing matching
2 March--------Winter holidays break
23 FebruaryAlexey StepanovCounting Dominating Sets
16 FebruaryFedor FominOn Self Duality of Pathwidth in Polyhedral Graph Embeddings
9 FebruaryFredrik ManneNew Star and Acyclic Coloring
Algorithms
2 FebruarySaket SaurabhParameterized complexity of
Directed Max Leaf
26 JanuaryYngve VillangerCharacterizing 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 DecemberQin XinFaster Centralized Communication in Radio Networks
8 DecemberDaniel MeisterComputing treewidth and minimum fill-in for permutation graphs in linear time
1 DecemberSerge GaspersBranching and Treewidth Based Exact Algorithms
24 NovemberOmid AminiMinimal Selectors and Fault Tolerant Networks
17 NovemberJan Arne TelleOn the crossing number of graphs with an excluded minor
10 NovemberPrudence WongEnergy Efficient Online Deadline Scheduling
3 NovemberMorten MjeldeA Memory Efficient Self-stabilizing Algorithm for Maximal k-packing
27 OctoberCharis PapadopoulosMaking arbitrary graphs transitively orientable:
Minimal comparability completions
20 OctoberDaniel LokshtanovDetermining treelength is hard (Treelength has been introduced in this paper)
6 October Parameterized Complexity of Dominating Set
29 SeptemberGregory GutinParameterized Complexity for Graph Linear Arrangement Problems (abstract)
22 SeptemberFederico ManciniA completely dynamic algorithm for split graphs
8 SeptemberMagnus WahlströmApproaches to a #2SAT algorithm analysis
1 SeptemberFrederic DornDynamic Programming and Fast Matrix Multiplication
28 AugustSbastien TixeuilSelf-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 JuneQin XinOptimal Gossiping with Unit Size Messages in Known Topology Radio Networks
19 MayChristophe Paul

Algorithmic aspects of modular decomposition

5 MayHerman Ruge JervellWellordering finite trees (abstract)
28 AprilHans BodlaenderOn Exact Algorithms for Treewidth
31 MarchDieter KratschLower Bounds for Exact Maximum Independent Set Algorithms
24 MarchArtem PyatkinOn polynomial algorithms on the vector sum problem
17 MarchIoan TodincaProper interval graphs: a minimal completion algorithm (abstract)
10 MarchFederico ManciniMinimal Split Completions of Graphs
3 MarchFrederic DornTwo birds with one stone: the best of branchwidth and treewidth with one algorithm
24 FebruaryYngve VillangerImproved Exponential-time Algorithms for Treewidth and Minimum Fill-in
17 FebruarySaket SaurabhParameterized algorithms for finding feedback vertex set
10 FebruaryEva-Marta LundellSubexponential-time framework for optimal embeddings of graphs in integer lattices
3 FebruaryJan KratochvilDistance constrained graph labeling and graph homomorphisms
27 JanuaryFredrik ManneParallel graph coloring for distributed memory computers
20 JanuarySerge GaspersExponential algorithms for the Maximum P_3-free Induced Subgraph Problem
13 JanuaryFabrizio GrandoniExponential 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 NovemberQin XinFaster Communication in Ad-hoc Radio Networks(abstract)
11 NovemberJan Arne TelleNew results on branchwidth of graphs
4 NovemberAlexey StepanovBounding the Number of Minimal Dominating Sets: a Measure and Conquer Approach
14 OctoberKarol SuchanMinimal interval completions
7 OctoberCharis PapadopoulosDrawing graphs using modular decomposition
30 SeptemberFrederic Dorn     Subexponential Algorithms for Planar Hamiltonicity
23 September Daniel PaulusmaBackbone 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 JuneDaniel LokshtanovOptimal broadcast domination of arbitrary graphs in polynomial time
22 April Artem PyatkinOn maximum number of minimal dominating sets in graphs
15 AprilDimitrios ThilikosFaster fixed-parameter tractable algorithms for matching and packing problems (abstract)
8 AprilMarina LipshteynRepresentations of Edge Intersection Graphs of Paths in a Tree (abstract)
11 MarchDieter Kratsch     The use of modular decomposition to design linear time algorithms for (P_5,gem)-free graphs (abstract)
4 MarchPierre Fraigniaud  A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decompositions  
4 FebruaryAlexey Stepanov  Quasiconvex Analysis of Backtracking Algorithms  
28 JanuaryDi 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 DeceemberElias DahlhausConverting a nested dissection algorithm into a minimal elimination algorithm
10 DecemberYngve VillangerComputing minimal triangulations in time  O(n log n) = o(n2.376)
3 DecemberJoanna BauerMinimizing the energy for broadcasting in wireless networks
12 NovemberFrederic DornComparing  tree decompositions with branch decompositions
29 OctoberArtem PyatkinOn (k,l)-coloring of incidentors
15 OctoberAnne BerryRecognizing 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 MayJan Kristian HauglandRegulare induserte undergrafer av gittere uten korte sykeler
30 AprilFredrik Manne Efficient multi-stage self-stabilizing algorithms on tree networks
22 AprilIoan Todinca Computing the treewidth for graphs with "few" minimal separators
18 MarchFedor Fomin  Exact algorithms for treewidth
11 MarchFedor Fomin  A Simple and Fast Approach for Solving Problems on Planar Graphs
20 FebruaryDag Haugland  A tree decomposition approach to MI-FAP
13 FebruaryBjørge Solli   David Eppstein's paper on  Small Maximal Independent Sets and Faster Exact Graph Coloring
 13 February Finse Winterschool Feedback  
30 JanuaryElena 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)erDimitrios M. ThilikosOn the Monotonicity of Games Generated by Symmetric Submodular Functions      
7 NovemberYngve VillangerA vertex incremental approach to maintaining chordal graphs dynamically II
31 OctoberPierre FraigniaudDistributed Hash Tables for P2P Network
30 OctoberDieter KratschCertifiying Algorithms
24 OctoberPinar HeggernesThe minimum degree heuristic and the minimal triangulation process
17 OctoberChristian SloperNew techniques in designing FPT-algorithms                               
10 OctoberChristian SloperUsing Vertex Cover Structure in designing FPT-algorithms - the case of k-Internal Spanning Tree
3 OctoberYngve VillangerA vertex incremental approach to maintaining chordal graphs dynamically
26 SeptemberJan Arne TelleCatval graphs and the catwidth graph parameter  
5 SeptemberFedor FominFixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs  
29 AugustJan 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 2003Christian Schindelhauer  Worst Case Mobility in Ad Hoc Networks
2 May 2003Fedor Fomin Exact algorithms for NP-hard problems VII
25 April 2003Pinar HeggernesBroadcast domination for interval graphs and trees
11 April 2003Fedor Fomin Exact algorithms for NP-hard problems VI
28 March 2003Hans BodlaenderTreewidth k in linear time

27 March 2003

Hans BodlaenderTreewidth: Heuristics and Preprocessing
21 March 2003Fedor Fomin  Exact algorithms for NP-hard problems V
14 March 2003Fedor Fomin  Exact algorithms for NP-hard problems IV
28 February 2003Fedor Fomin  Exact algorithms for NP-hard problems III
18 February 2003Frederic Dorn  LEDA & Tuning Algorithms for Hard Planar Graph Problems
7 February 2003Fedor Fomin  Exact algorithms for NP-hard problems II
24 January 2003Fedor 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 2002Jan Arne TellePlanar graphs and treewidth II
22 November 2002Jan Arne TellePlanar graphs and treewidth I
8 November 2002Fredrik ManneA Linear time 2-approximation algorithm for maximum weighted matching in general graphs
25 October 2002Leda-gruppenIntroduksjon til Leda
18 October 2002Pinar HeggernesMaximum Cardinality Search for Minimal Triangulations
4 October 2002Kjell Jørgen HoleAlgorithmic problems in mobile and ad-hoc networks
27 September 2002Assefaw H. GebremedhinParallel Distance-k Coloring Algorithms for Numerical Optimization
  13 September 2002Yngve VillangerEfficient Implementation of a Minimal Triangulation Algorithm

Vårsemesteret 2002

In charge of the seminars is Jean Blair.
Fridays 12:15 Grupperom 2101.



8 February 2002Jan KratochvilIntersection graphs
15 February 2002Jiri FialaThe independence and coloring problems on disk graphs
22 February 2002Ondra PangracString graphs
1 March 2002Jean BlairWinter school impressions - AAR
8 March 2002Petter KristiansenA self-stabilizing algorithm for maximal 2-packing
15 March 2002Jan Arne TelleTree decompostions of small pathwith
22 March 2002  Jan Arne TelleTree decompostions of small pathwith (continued)
5 April 2002Petter KristiansenDomination, independence, irredundance
12 April 2002Jean BlairGeneralized vertex covers
19 April 2002group workClasses of graphs having vertex covers that are: K-partite, independent, c
lique, or acyclic 
26 April 2002group workGraphs with induced path and induced tree vertex covers
3 May 2002group workMore on induced path and induced-tree vertex covers
14 May 2002Fedor FominRadio 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 2000Jan Arne TelleFixed parameter tractability (FPT)
15 September 2000Christian SloperFPT : Bounded search trees
22 September 2000Petter KristiansenFPT : Reduction to a problem kernel
29 September 2000Petter KristiansenFPT : List of interesting problems 
6 Oktober 2000Christian SloperFPT: Planar red blue dominating set
20 Oktober 2000Petter KristiansenFPT : Graph modification problem
27 Oktober 2000Fredrik Manne NM i programmering 2000
3 November 2000Pinar HeggernesFPT : Minimum fill is FPT
10 November 2000Christian Sloper FPT: Method of test sets
17 November 2000Jan Arne TelleDeterministic finite tree automata 
24 November 2000Petter KristiansenMethod of test sets for regular tree languages
1 Desember 2000Jan Arne TelleBounded degree parsing trees
8 Desember 2000Petter KristiansenMethod 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 HalldorssonMulticoloring of graphs
5/2  Assefaw Hadish GebremedhinParallell Graph Coloring
12/2 Pinar HeggernesFyll: Hvorfor glissne matriser?
19/2 Pinar Fyll: Eliminasjonsordninger og fyll
26/2 Jan ArneFyll: Kordale grafer I
5/3  Jan ArneFyll: Kordale grafer II
12/3 Jan ArneFyll: Kordale grafer III
19/3 Utsatt 
26/3 Petter KristiansenPakking av grafer
2/4  Påske 
9/4  Fredrik ManneFyll: Min Degree og Nested Dissection
16/4 Pinar HeggernesAlgoritmer for minimalt fyll
23/4 Ole-Martin KvingeGrafalgoritmer for glisne matriser
30/4 Anne Berry, Univ Montpellier, FrankrikeAlgorithms for minimal fill
7/5  Jan Kratochvil, Charles Univ, Prag, TsjekkiaPartial covers of graphs 
14/5 Jiri Fiala, Charles Univ, Prag, TsjekkiaChannel assignment problem
21/5 FredrikMer om fyll
28/5 Knut ErstadVisualisering ved hjelp av L-systemer
31/5 Sidsel HorveiAlgoritmer for s�kemaskiner p� WWW

1998

Høstsemesteret 1998

Ansvarlig: Jan Arne Telle

 

11/9 Jan Arne TelleMod-2 Independence and domination in graphs
18/9 Alex Pothen, Old Dominion Univ., USAGraph 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, TysklandMinimal elimination orderings of chordal graphs
9/10 Andrzej Proskurowski, Univ. of Oregon, USAMultisource shortest path problems
16/10 Sven Sigurdsson, Science Institute, University of IcelandElimination trees in parameter estimation problems.
23/10 Bengt AspvallApproximations for the general block distribution of a matrix
30/10 Fredrik Manne, UiBStrukturert 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