Efficient Algorithms for Graph-Theoretic and Geometric Problems
(2015)- Abstract
- This 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 new exact algorithms for the case of general graphs as well as approximation algorithms for the case of planar graphs.
Next, we study drawing graphs within a given polygon in the plane. We present asymptotically tight upper and lower bounds for this problem
Further, we study the problem of... (More) - This 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 new exact algorithms for the case of general graphs as well as approximation algorithms for the case of planar graphs.
Next, we study drawing graphs within a given polygon in the plane. We present asymptotically tight upper and lower bounds for this problem
Further, we study the problem of Subgraph Isormorphism, which amounts to decide if an input graph (pattern) is isomorphic to a subgraph of another input graph (host graph). We show several new bounds on the time complexity of detecting small pattern graphs. Among other things, we provide a new framework for detection by testing polynomials for non-identity with zero.
Finally, we study the problem of partitioning a 3D histogram into a minimum number of 3D boxes and it's applications to efficient computation of matrix products for positive integer matrices. We provide an efficient approximation algorithm for the partitioning problem and several algorithms for integer matrix multiplication. The multiplication algorithms are explicitly or implicitly based on an interpretation of positive integer matrices as 3D histograms and their partitions. (Less) - Abstract (Swedish)
- 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å relevanta punkter. Vi visar nya exakta algoritmer i det fallet för generella grafer samt approximationsalgoritmer i fallet med planära grafer.
I nästa avsnitt behandlas problemet att rita en graf inuti en avgränsande polygon i planet. Vi presenterar asymptotiskt ekvivalenta övre och undre gränser för... (More) - 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å relevanta punkter. Vi visar nya exakta algoritmer i det fallet för generella grafer samt approximationsalgoritmer i fallet med planära grafer.
I nästa avsnitt behandlas problemet att rita en graf inuti en avgränsande polygon i planet. Vi presenterar asymptotiskt ekvivalenta övre och undre gränser för lösningar till problemet.
Vidare studeras problemet med att finna delgrafisomorfier, problemet utgörs av att givet två grafer (kallade "pattern" och "host") avgöra om det finns en isomorfi mellan noderna i "pattern" och noderna av en delgraf i "host". Vi visar flera nya undre gränser för tidskomplexiteten för detektering av olika små grafer med 4 noder. Vi visar även en ny metod för detektering av genom att evaluera om ett polynom ej är ekvivalent med nollpolynomet.
Slutligen studeras problemet att paritionera ett 3D histogram i ett minimalt antal rätblock samt en applikation för metoder för matrismultiplikation när matriserna endast innehåller positiva heltal. Vi visar en effektiv approximationsalgoritm för partitioneringsproblemet och flera olika algoritmer för matrismultiplikationen. Alla multiplikationsalgoritmer bygger explicit eller implicit på att vi tolkar en positiv heltalsmatris som ett 3D histogram och sedan använder den följande partitionen. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5228131
- author
- Floderus, Peter LU
- supervisor
- opponent
-
- Dr. Wong, Prudence, The University of Liverpool
- organization
- publishing date
- 2015
- type
- Thesis
- publication status
- published
- subject
- pages
- 90 pages
- publisher
- Centre for Mathematical Sciences, Lund University
- defense location
- Centre for Mathematical Sciences, MH:C
- defense date
- 2015-04-24 13:15:00
- ISBN
- 978-91-7623-277-4
- language
- English
- LU publication?
- yes
- id
- 0cbbe777-6a7b-4e82-bbc2-87c639e6678a (old id 5228131)
- date added to LUP
- 2016-04-01 14:25:24
- date last changed
- 2018-11-21 20:26:37
@phdthesis{0cbbe777-6a7b-4e82-bbc2-87c639e6678a,
abstract = {{This 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.<br/><br>
<br/><br>
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 new exact algorithms for the case of general graphs as well as approximation algorithms for the case of planar graphs.<br/><br>
<br/><br>
Next, we study drawing graphs within a given polygon in the plane. We present asymptotically tight upper and lower bounds for this problem<br/><br>
<br/><br>
Further, we study the problem of Subgraph Isormorphism, which amounts to decide if an input graph (pattern) is isomorphic to a subgraph of another input graph (host graph). We show several new bounds on the time complexity of detecting small pattern graphs. Among other things, we provide a new framework for detection by testing polynomials for non-identity with zero. <br/><br>
<br/><br>
Finally, we study the problem of partitioning a 3D histogram into a minimum number of 3D boxes and it's applications to efficient computation of matrix products for positive integer matrices. We provide an efficient approximation algorithm for the partitioning problem and several algorithms for integer matrix multiplication. The multiplication algorithms are explicitly or implicitly based on an interpretation of positive integer matrices as 3D histograms and their partitions.}},
author = {{Floderus, Peter}},
isbn = {{978-91-7623-277-4}},
language = {{eng}},
publisher = {{Centre for Mathematical Sciences, Lund University}},
school = {{Lund University}},
title = {{Efficient Algorithms for Graph-Theoretic and Geometric Problems}},
url = {{https://lup.lub.lu.se/search/files/3966487/5228137.pdf}},
year = {{2015}},
}