Efficient Algorithms for Graph-Theoretic and Geometric Problems
Author
Summary, in English
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.
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.
Department/s
Publishing year
2015
Language
English
Full text
- Available as PDF - 951 kB
- Download statistics
Document type
Dissertation
Publisher
Centre for Mathematical Sciences, Lund University
Topic
- Mathematics
Status
Published
Supervisor
ISBN/ISSN/Other
- ISBN: 978-91-7623-277-4
Defence date
24 April 2015
Defence time
13:15
Defence place
Centre for Mathematical Sciences, MH:C
Opponent
- Prudence Wong (Dr.)