Sammanfattning
This dissertation is a contribution to the knowledge of the computational complexity of discrete combinatorial problems.
1. The first problem that we consider is to compute the maximum independent set of a box graph, that is, given a set of orthogonal boxes in the plane compute the largest subset such that no boxes in the subset overlap. We provide an $mathtt{exp}(O(sqrt nlog n))$time algorithm for this problem and give an $mathtt{exp}(Omega(sqrt n))$ bound unless the {em Exponential Time Hypothesis} (ETH) is false.
2. Next, we consider the problem of computing the Hadwiger number of a graph $G$. The Hadwiger number is the largest $h$ such that the complete graph on $h$ vertices, $K_h,$ is a minor of $G$. We also study the related problem of computing the maximum homeomorphic clique. That is, determining the largest $h$ such that $K_h$ is a topological minor of $G$. We give upper and lower bounds for the approximability of these problems. For the fixedvertex subgraph homeomorphism problem we provide an exponential time exact algorithm.
3. Then we study broadcasting in geometric multihop radio networks by using analysis techniques from computational complexity. We attempt to minimize the total power consumption of broadcasting a message from a source node to all the other nodes in the
network. We also study the number of rounds required to broadcast a message in a known geometric radio network. We also show that an $h$hop broadcasting scheme, in a model that does not account for interference, requiring $cal E$ energy can be simulated in $hlog psi$ rounds using $O(cal E)$ energy in a model that does, where $psi$ denotes the ratio between the maximum and the minimum Euclidean distance between nodes in the network.
4. Finally, we establish lower bounds on the computational complexity of counting problems; in particular we study the Tutte polynomial and the permanent under a counting version of the ETH (#ETH). The Tutte polynomial is related to determining the failure probability for
computer networks by its relation to the reliability polynomial. We consider the problem of computing the Tutte polynomial in a point $(x,y)$, and show that for multigraphs with $bar m$ adjacent vertex pairs the problem requires time $mathtt{exp}(Omega(bar m)),$ in many points, under the #ETH. We also show that computing the permanent of a $n imes n$ matrix with $bar m$ nonzero entries requires time $mathtt{exp}(Omega(bar m))$,} under the #ETH.
1. The first problem that we consider is to compute the maximum independent set of a box graph, that is, given a set of orthogonal boxes in the plane compute the largest subset such that no boxes in the subset overlap. We provide an $mathtt{exp}(O(sqrt nlog n))$time algorithm for this problem and give an $mathtt{exp}(Omega(sqrt n))$ bound unless the {em Exponential Time Hypothesis} (ETH) is false.
2. Next, we consider the problem of computing the Hadwiger number of a graph $G$. The Hadwiger number is the largest $h$ such that the complete graph on $h$ vertices, $K_h,$ is a minor of $G$. We also study the related problem of computing the maximum homeomorphic clique. That is, determining the largest $h$ such that $K_h$ is a topological minor of $G$. We give upper and lower bounds for the approximability of these problems. For the fixedvertex subgraph homeomorphism problem we provide an exponential time exact algorithm.
3. Then we study broadcasting in geometric multihop radio networks by using analysis techniques from computational complexity. We attempt to minimize the total power consumption of broadcasting a message from a source node to all the other nodes in the
network. We also study the number of rounds required to broadcast a message in a known geometric radio network. We also show that an $h$hop broadcasting scheme, in a model that does not account for interference, requiring $cal E$ energy can be simulated in $hlog psi$ rounds using $O(cal E)$ energy in a model that does, where $psi$ denotes the ratio between the maximum and the minimum Euclidean distance between nodes in the network.
4. Finally, we establish lower bounds on the computational complexity of counting problems; in particular we study the Tutte polynomial and the permanent under a counting version of the ETH (#ETH). The Tutte polynomial is related to determining the failure probability for
computer networks by its relation to the reliability polynomial. We consider the problem of computing the Tutte polynomial in a point $(x,y)$, and show that for multigraphs with $bar m$ adjacent vertex pairs the problem requires time $mathtt{exp}(Omega(bar m)),$ in many points, under the #ETH. We also show that computing the permanent of a $n imes n$ matrix with $bar m$ nonzero entries requires time $mathtt{exp}(Omega(bar m))$,} under the #ETH.
Originalspråk  engelska 

Kvalifikation  Doktor 
Tilldelande institution  
Handledare 

Tilldelningsdatum  2009 feb. 27 
ISBN (tryckt)  9789162876845 
Status  Published  2009 
Bibliografisk information
Defence detailsDate: 20090227
Time: 13:00
Place: E:1406, Ebuilding, Ole Römers väg 3
External reviewer(s)
Name: Fomin, Fedor
Title: Professor
Affiliation: Institutt for informatikk, University of Bergen

Ämnesklassifikation (UKÄ)
 Datavetenskap (datalogi)