Blog

On a (Somewhat Old) Dynamic Steiner Tree Problem

By sank The dynamic Steiner tree problem has been around for a while already (for 24 years), for sale but it did not get a satisfying answer from efficiency point of view, clinic i.e., one would like to have a fast algorithm that maintains a constant approximate solution and allows to update the set of

Read on »

Graph Isomorphism on graphs of bounded treewidth

By malcin The Graph Isomorphism problem is interesting for many reasons, look one being the fact that its complexity status is still unclear – it is probably not NP-complete, ambulance but not known to be in P either. In the past decades, pilule researchers identified a large number of special graph classes for which GI

Read on »

Online bipartite matching in offline time

By Anna Zych In 1973 Hopcroft and Karp gave a very nice time algorithm computing a maximum matching in unweighted bipartite graphs. This algorithm turned out to be the milestone that is hard to beat. The bipartite maximum matching problem has been studied in many different flavors such as online, treatment approximate, dynamic, …read more

Read on »

How pineapples help finding Steiner trees?

By sank Recently with Marcin Pilipczuk, unhealthy Micha? Pilipczuk and Erik Jan van Leeuwen we were able to prove that the Steiner Tree problem has a polynomial kernel on unweighted planar graphs. So far this was one of few problems where such kernel seemed possible, malady but existing tools (e.g., price theory of bidimensionality) were

Read on »

FPT algorithms and syphilis

By kowalik Long long time ago, diagnosis actually in 1943, US Army was recruiting a lot of soldiers. Each of the recruits had to be subject of some medical examination, and in particular they were tested against syphilis. However, performing a single test was quite expensive. Then they came up with the following …read more

Read on »

Efficiency of Random Priority

By Marek Adamczyk Matchings are one of the most basic primitives used in the area of mechanism design. Whenever we need to assign items to agents we view it as a matching problem. Of course, viagra buy plenty of variations differing in constraints and objectives can be considered, tadalafil but let us look at the

Read on »

Is it easier for Europeans to get to FOCS than to STOC?

By sank I have recently realized that I have published 9 papers at FOCS and only 1 paper at STOC. I started wondering why this happened. I certainly have been submitting more papers to FOCS than to STOC. The ratio is currently 14 to 6. However, advice this alone does not explain the …read more

Read on »