Efficient Algorithms for Graph-Theoretic and Geometric Problems
Popular Abstract in Swedish Avhandlingen studerar flera olika algoritmiska problem inom grafteori och geometri, applikationerna sträcker sig från kretskortsdesign till matrismultiplikation. Vi börjar med att studera en grafteoretisk modell för det så kallade "firefigher problem". Målet med detta problemet är att rädda så mycket som möjligt av en given area genom att placera ut brandmän på relevaThis thesis studies several different algorithmic problems in graph theory and in geometry. The applications of the problems studied range from circuit design optimization to fast matrix multiplication. First, we study a graph-theoretical model of the so called ''firefighter problem''. The objective is to save as much as possible of an area by appropriately placing firefighters. We provide both n
