Journal Publications
 Khaled Elbassioni, Domagoj Matijevic, Domagoj Severdija
 Guarding 1.5D Terrains with Demands
 International Journal of Computer Mathematics , 2012
 (extended abstract appeared in EuroCG 2010)

In this paper, we consider the 1.5D terrain guarding problem in which every point on the terrain that is to be covered has an integer demand associated with it. The goal is to find a minimum cardinality set of guards such that each point is guarded by a number of guards satisfying its demand. We present a first constantfactor approximation algorithm for the problem, that is, a $(1+1/d_\min)$approximation algorithm, where $d_\min$ is a minimum demand. The algorithm is based on solving appropriate subproblems established by a decomposition of the main problem due to linear programming relaxation of the corresponding covering problem.
 Khaled Elbassioni, Slobodan Jelic, Domagoj Matijevic
 The relation of Connected Set Cover and Group Steiner Tree
 to appear in Theoretical Computer Science, 2012.

ABSTRACT: We report that the Connected Set Cover (CSC) problem is just a special case of the Group Steiner Tree (GST) problem. Based on that we obtain the first algorithm for CSC with polylogarithmic approximation guarantee as well as the first approximation algorithms for the weighted version of the problem and the version with requirements. Moreover, we argue that the inapproximability result of GST will carry on to the weighted version of the CSC problem.
 Rene Beier, Stefan Funke, Domagoj Matijevic, Peter Sanders
 EnergyEfficient Paths In Radio Networks
 to appear in Algorithmica, 2010.
 (part of the results appeared in ESA 2003)

ABSTRACT: We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ??(p, q) = pq^?? +C_p, for some constant ?? > 1 and nonnegative offset costs C_p. Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops. We present an exact algorithm for the important case when ?? = 2, which requires O(kn log n) time per query pair (p, q). For the case of an unrestricted number of hops we describe a family of algorithms with query time O(n^(1+alpha)), where alpha > 0 can be chosen arbitrarily. If we relax the exactness requirement, we can find an approximate (1+eps) solution in constant time by querying a data structure which has linear size and which can be build in O(n log n) time. One tool we employ might be of independent interest: For any pair of points (p, q) we can report in constant time the cluster pair (A,B) representing (p, q) in a wellseparated pair decomposition of P.
 Khaled Elbassioni, Erik Krohn, Domagoj Matijevi??, Julian Mestre, Domagoj ??everdija
 Improved Approximations for Guarding 1.5Dimensional Terrains
 to appear in Algorithmica, 2009.
 (extended abstract appeared in STACS 2009)

ABSTRACT: We present a 4approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.
 Domagoj Matijevi??, Ralf Osbild
 Finding the ThetaGuarded Region
 to appear in Computational Geometry: Theory and Applications (CGTA), 2009.

ABSTRACT:We are given a finite set of points (\emph{guards}) in the plane. A \Thetacone is a cone with apex angle \Theta. We call a \Thetacone empty, if it does not contain any guards in its interior. A point p is called \Thetaguarded, if every \Thetacone with apex located at p is nonempty. The set of all \Thetaguarded points is called the \Thetaguarded region, or the $\Theta$region for short. The rationale behind this model is that a point is wellguarded only if it is guarded from all sides. In this paper we show the bound for the complexity of the \Thetaregion as well as present the algorithms for computing it.
 Jens Maue, Peter Sanders, Domagoj Matijevi??
 Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
 ACM Journal of Experimental Algorithmics (ACM JEA), 14/3, 2009
 (extended abstract appeared in WEA 2006)

ABSTRACT: We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely exible tradeo between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong sense of direction". We evaluate our approach experimentally using large, realworld road networks.
 Soeren Laue, Domagoj Matijevi??
 Approximating khop Minimum Spanning Trees in Euclidean metrics
 Information Processing Letters (IPL) , 107/34:96101, 2008.
 (extended abstract appeared in CCCG 2007)

ABSTRACT:In the minimumcost khop spanning tree (khop MST) problem, we are given a set of n points in a metric space, a positive small integer k and a root point r. We are interested in computing a rooted spanning tree of minimum cost such that the longest rootleaf path in the tree has at most k edges. We present a polynomialtime approximation scheme for the plane. Our algorithm is based on Arora's et al. technique for the Euclidean kmedian problem.
 Stefan Funke, Domagoj Matijevi??, Peter Sanders
 Constant Time Queries for Energy Efficient Paths in MultiHop Wireless Networks
 Journal of Computing and Information Technology (CIT), 16/2:119130, 2008
 (extended abstract appeared in A_SWAN 2004)

ABSTRACT: We investigate algorithms for computing energy efficient paths in adhoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the position of radio stations in such a way that approximately energy optimal paths can be retrieved in constant time, i.e., independent of the network size. We put particular emphasis on actual implementations which demonstrate that large constant factors hidden in the theoretical analysis are not a big problem in practice.
 EnergyAware Stage Illumination
 Friedrich Eisenbrand, Stefan Funke, Andreas Karrenbauer, Domagoj Matijevi??
 International Journal of Computational Geometry and Applications (IJCGA), 18/12:107129, 2008
 (extended abstract appeared in SCG 2005, implementation published in Wolfram Demonstrations Project)
Refereed Proceedings

DISTRIBUTER  The Distributed
System for Efficient Execution of Parallel Programs
D. Matijevic, G. Martinovic, P. Taler
33rd International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2010, Opatija 
Guarding 1.5D Terrains with Demands
K. Elbassioni, D. Matijevic, D. Severdija
26th European Workshop on Computational Geometry (EuroCG'10 ), pp. 133136, Dortmund, 2010  TRANSIT: Ultrafast ShortestPath Queries with LinearTime Preprocessing
H. Bast, S. Funke, D. Matijevic
The Shortest Path Problem: Ninth DIMACS Implementation Challenge, pp. 175???192, AMS, 2009 
Improved
approximations for
guarding 1.5dimensional terrains
K. Elbassioni, D. Matijevic, J. Mestre, and D. Severdija
CoRR, abs/0809.0159v1, 2008. and STACS 2009. 
Approximating khop Minimum Spanning Trees in Euclidean metrics
S. Laue, D. Matijevic
preliminary version in Proc. 19th Canadian Conference on Computational Geometry (CCCG), 2007, Ottawa 
In Transit to Constant Time ShortestPath Queries in Road
Networks
H. Bast, S. Funke, D. Matijevic, P. Sanders, D. Schultes
9th Workshop on Algorithm Engineering and Experimentation (ALENEX), 2007, New Orleans  (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
S. Funke, T. Malamatos, D. Matijevic, N. Wolpert
18th Canadian Conference on Computational Geometry (CCCG), 2006, Kingston, Ontario  Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
J. Maue, P. Sanders, D. Matijevic
5th International Workshop on Experimetal Algorithms ( WEA 2006 ), Menorca Island, Volume 4007 in LNCS, pages 316  327, Springer, 2006.  EnergyAware Stage Illumination
F. Eisenbrand, S. Funke, A. Karrenbauer, D. Matijevic
preliminary version in Proc. 21st ACM Symposium on Computational Geometry (SoCG) 2005, Pisa  Constant Time Queries for
Energy Efficient Paths in MultiHop Wireless Networks
S. Funke, D. Matijevic, P. Sanders
preliminary version in Proc. AlgorithmS for Wireless And mobile Networks (A_SWAN) 2004, Boston 
Approximating Energy Efficient Paths in Wireless MultiHop Networks
S. Funke, D. Matijevic, P. Sanders
11th Annual European Symposium on Algorithms (ESA 2003), Budapest, Volume 2832 in LNCS, pages 230241. Springer, 2003.