Source author record

Aleksandar Ilic

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Distributed, Parallel, and Cluster Computing math.CA

Catalog footprint

Research overview

17works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Unlocking Personalized Healthcare on Modern CPUs/GPUs: Three-way Gene Interaction Study

Developments in Genome-Wide Association Studies have led to the increasing notion that future healthcare techniques will be personalized to the patient, by relying on genetic tests to determine the risk of developing a disease. To this end, the detection of gene interactions that cause complex diseases constitutes an important application. Similarly to many applications in this field, extensive data sets containing genetic information for a series of patients are used (such as Single-Nucleotide Polymorphisms), leading to high computational complexity and memory utilization, thus constituting a major challenge when targeting high-performance execution in modern computing systems. To close this gap, this work proposes several novel approaches for the detection of three-way gene interactions in modern CPUs and GPUs, making use of different optimizations to fully exploit the target architectures. Crucial insights from the Cache-Aware Roofline Model are used to ensure the suitability of the applications to the computing devices. An extensive study of the architectural features of 13 CPU and GPU devices from all main vendors is also presented, allowing to understand the features relevant to obtain high-performance in this bioinformatics domain. To the best of our knowledge, this study is the first to perform such evaluation for epistasis detection. The proposed approaches are able to surpass the performance of state-of-the-art works in the tested platforms, achieving an average speedup of 3.9 $\times$ (7.3 $\times$ on CPUs and 2.8 $\times$ on GPUs) and maximum speedup of 10.6 $\times$ on Intel UHD P630 GPU.

preprint2021arXiv

Optimal algorithm for computing Steiner 3-eccentricities of trees

The Steiner $k$ -eccentricity of a vertex $v$ of a graph $G$ is the maximum Steiner distance over all $k$ -subsets of $V (G)$ which contain $v$ . In this note, we design a linear algorithm for computing the Steiner $3$ -eccentricities and the connective Steiner $3$ -eccentricity index on a tree and thus improving a quadratic algorithm presented in [G. Yu, X. Li, \emph{Connective Steiner 3-eccentricity index and network similarity measure}, Appl. Math. Comput. 386 (2020), 125446.]

preprint2019arXiv

HeTM: Transactional Memory for Heterogeneous Systems

Modern heterogeneous computing architectures, which couple multi-core CPUs with discrete many-core GPUs (or other specialized hardware accelerators), enable unprecedented peak performance and energy efficiency levels. Unfortunately, though, developing applications that can take full advantage of the potential of heterogeneous systems is a notoriously hard task. This work takes a step towards reducing the complexity of programming heterogeneous systems by introducing the abstraction of Heterogeneous Transactional Memory (HeTM). HeTM provides programmers with the illusion of a single memory region, shared among the CPUs and the (discrete) GPU(s) of a heterogeneous system, with support for atomic transactions. Besides introducing the abstract semantics and programming model of HeTM, we present the design and evaluation of a concrete implementation of the proposed abstraction, which we named Speculative HeTM (SHeTM). SHeTM makes use of a novel design that leverages on speculative techniques and aims at hiding the inherently large communication latency between CPUs and discrete GPUs and at minimizing inter-device synchronization overhead. SHeTM is based on a modular and extensible design that allows for easily integrating alternative TM implementations on the CPU's and GPU's sides, which allows the flexibility to adopt, on either side, the TM implementation (e.g., in hardware or software) that best fits the applications' workload and the architectural characteristics of the processing unit. We demonstrate the efficiency of the SHeTM via an extensive quantitative study based both on synthetic benchmarks and on a porting of a popular object caching system.

preprint2016arXiv

Counterexamples to conjectures on graph distance measures based on topological indexes

In this paper we disprove three conjectures from [M. Dehmer, F. Emmert-Streib, Y. Shi, Interrelations of graph distance measures based on topological indices, PLoS ONE 9 (2014) e94985] on graph distance measures based on topological indices by providing explicit classes of trees that do not satisfy proposed inequalities. The constructions are based on the families of trees that have the same Wiener index, graph energy or Randic index - but different degree sequences.

preprint2015arXiv

On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider a special case of the ordinary NP-hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. In [S. S. Panwalkar, C. Koulamas, An O(n^2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines, European Journal of Operational Research 221 (2012), 7-13.], the authors presented quadratic algorithm for the problem when each job has its smaller processing time on the first machine. In this note, we improve the running time of the algorithm to O(n log n) by efficient implementation using recently introduced modified binary tree data structure.

preprint2013arXiv

A note on 'A New Approach To Compute Wiener Index'

In this note, we discuss the method explained in the recent paper [P. Manuel, I. Rajasingh, B. Rajan, R. Sundara Rajan, A New Approach To Compute Wiener Index, Journal of Computational and Theoretical Nanoscience 10, (2013) 1515-1521.] for computing the Wiener index of special chemical graphs. The method is actually already well-known and equivalent to the 'cut method' introduced in 1995 by Klavzar, Gutman and Mohar, and used in multiple papers for computing various distance based graph invariants.

preprint2012arXiv

Generalizations of Wiener polarity index and terminal Wiener index

In theoretical chemistry, distance-based molecular structure descriptors are used for modeling physical, pharmacologic, biological and other properties of chemical compounds. We introduce a generalized Wiener polarity index $W_k (G)$ as the number of unordered pairs of vertices ${u, v}$ of $G$ such that the shortest distance $d (u, v)$ between $u$ and $v$ is $k$ (this is actually the $k$ -th coefficient in the Wiener polynomial). For $k = 3$ , we get standard Wiener polarity index. Furthermore, we generalize the terminal Wiener index $TW_k (G)$ as the sum of distances between all pairs of vertices of degree $k$ . For $k = 1$ , we get standard terminal Wiener index. In this paper we describe a linear time algorithm for computing these indices for trees and partial cubes, and characterize extremal trees maximizing the generalized Wiener polarity index and generalized terminal Wiener index among all trees of given order $n$ .

preprint2012arXiv

Note on the harmonic index of a graph

The harmonic index of a graph $G$ is defined as the sum of weights $\frac{2}{deg(v) + deg(u)}$ of all edges $uv$ of $E (G)$ , where $deg (v)$ denotes the degree of a vertex $v$ in $V (G)$ . In this note we generalize results of [L. Zhong, The harmonic index on graphs, Appl. Math. Lett. 25 (2012), 561--566] and establish some upper and lower bounds on the harmonic index of $G$ .

preprint2011arXiv

Efficient algorithm for the vertex connectivity of trapezoid graphs

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. These graphs and their generalizations were applied in various fields, including modeling channel routing problems in VLSI design and identifying the optimal chain of non-overlapping fragments in bioinformatics. Using modified binary indexed tree data structure, we design an algorithm for calculating the vertex connectivity of trapezoid graph $G$ with time complexity $O (n \log n)$ , where $n$ is the number of trapezoids. Furthermore, we establish sufficient and necessary condition for a trapezoid graph $G$ to be bipartite and characterize trees that can be represented as trapezoid graphs.

preprint2011arXiv

Laplacian Estrada index of trees

Let $G$ be a simple graph with $n$ vertices and let $μ_1 \geqslant μ_2 \geqslant...\geqslant μ_{n - 1} \geqslant μ_n = 0$ be the eigenvalues of its Laplacian matrix. The Laplacian Estrada index of a graph $G$ is defined as $LEE (G) = \sum\limits_{i = 1}^n e^{μ_i}$ . Using the recent connection between Estrada index of a line graph and Laplacian Estrada index, we prove that the path $P_n$ has minimal, while the star $S_n$ has maximal $LEE$ among trees on $n$ vertices. In addition, we find the unique tree with the second maximal Laplacian Estrada index.

preprint2011arXiv

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph $\ICG_n (D)$ has the vertex set $Z_n = \{0, 1, 2, ..., n - 1\}$ and vertices $a$ and $b$ are adjacent if $\gcd(a-b,n)\in D$ , where $D \subseteq \{d : d \mid n,\ 1\leq d<n\}$ . These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following [R. B. Bapat, S. Pati, \textit{Energy of a graph is never an odd integer}, Bull. Kerala Math. Assoc. 1 (2004) 129--132.], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from [A. Ili\' c, \textit{The energy of unitary Cayley graphs}, Linear Algebra Appl. 431 (2009), 1881--1889.]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with $n$ vertices, provided $n$ is even.

preprint2011arXiv

On Distance Spectral Radius and Distance Energy of Graphs

For a connected graph, the distance spectral radius is the largest eigenvalue of its distance matrix, and the distance energy is defined as the sum of the absolute values of the eigenvalues of its distance matrix. We establish lower and upper bounds for the distance spectral radius of graphs and bipartite graphs, lower bounds for the distance energy of graphs, and characterize the extremal graphs. We also discuss upper bounds for the distance energy.

preprint2011arXiv

On Laplacian like energy of trees

Let $G$ be a simple undirected $n$ -vertex graph with the characteristic polynomial of its Laplacian matrix $L(G)$ , $\det (λI - L (G))=\sum_{k = 0}^n (-1)^k c_k λ^{n - k}$ . Laplacian--like energy of a graph is newly proposed graph invariant, defined as the sum of square roots of Laplacian eigenvalues. For bipartite graphs, the Laplacian--like energy coincides with the recently defined incidence energy $IE (G)$ of a graph. In [D. Stevanovi\' c, \textit{Laplacian--like energy of trees}, MATCH Commun. Math. Comput. Chem. 61 (2009), 407--417.] the author introduced a partial ordering of graphs based on Laplacian coefficients. We point out that original proof was incorrect and illustrate the error on the example using Laplacian Estrada index. Furthermore, we found the inverse of Jacobian matrix with elements representing derivatives of symmetric polynomials of order $n$ , and provide a corrected elementary proof of the fact: Let $G$ and $H$ be two $n$ -vertex graphs; if for Laplacian coefficients holds $c_k (G) \leqslant c_k (H)$ for $k = 1, 2, ..., n - 1$ , then $LEL (G) \leqslant LEL (H)$ . In addition, we generalize this theorem and provide a necessary condition for functions that satisfy partial ordering based on Laplacian coefficients.

preprint2011arXiv

On the extremal properties of the average eccentricity

The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity $ecc (G)$ of a graph $G$ is the mean value of eccentricities of all vertices of $G$ . The average eccentricity is deeply connected with a topological descriptor called the eccentric connectivity index, defined as a sum of products of vertex degrees and eccentricities. In this paper we analyze extremal properties of the average eccentricity, introducing two graph transformations that increase or decrease $ecc (G)$ . Furthermore, we resolve four conjectures, obtained by the system AutoGraphiX, about the average eccentricity and other graph parameters (the clique number, the Randi\' c index and the independence number), refute one AutoGraphiX conjecture about the average eccentricity and the minimum vertex degree and correct one AutoGraphiX conjecture about the domination number.

preprint2011arXiv

On the Wiener index and Laplacian coefficients of graphs with given diameter or radius

Let $G$ be a simple undirected $n$ -vertex graph with the characteristic polynomial of its Laplacian matrix $L(G)$ , $\det (λI - L (G))=\sum_{k = 0}^n (-1)^k c_k λ^{n - k}$ . It is well known that for trees the Laplacian coefficient $c_{n-2}$ is equal to the Wiener index of $G$ . Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize first the trees with given diameter and then the connected graphs with given radius which simultaneously minimize all Laplacian coefficients. This approach generalizes recent results of Liu and Pan [MATCH Commun. Math. Comput. Chem. 60 (2008), 85--94] and Wang and Guo [MATCH Commun. Math. Comput. Chem. 60 (2008), 609--622] who characterized $n$ -vertex trees with fixed diameter $d$ which minimize the Wiener index. In conclusion, we illustrate on examples with Wiener and modified hyper-Wiener index that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution.

preprint2011arXiv

On vertex covers and matching number of trapezoid graphs

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. Using binary indexed tree data structure, we improve algorithms for calculating the size and the number of minimum vertex covers (or independent sets), as well as the total number of vertex covers, and reduce the time complexity from $O (n^2)$ to $O (n \log n)$ , where $n$ is the number of trapezoids. Furthermore, we present the family of counterexamples for recently proposed algorithm with time complexity $O (n^2)$ for calculating the maximum cardinality matching in trapezoid graphs.

preprint2011arXiv

The largest $n-1$ Hosoya indices of unicyclic graphs

The Hosoya index $Z (G)$ of a graph $G$ is defined as the total number of edge independent sets of $G$ . In this paper, we extend the research of [J. Ou, On extremal unicyclic molecular graphs with maximal Hosoya index, \textit{Discrete Appl. Math.} 157 (2009) 391--397.] and [Y. Ye, X. Pan, H. Liu, Ordering unicyclic graphs with respect to Hosoya indices and Merrifield-Simmons indices, \textit{MATCH Commun. Math. Comput. Chem.} 59 (2008) 191--202.] and order the largest $n-1$ unicyclic graphs with respect to the Hosoya index.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Aleksandar Ilic

Research overview

Is this your work?

17 publications

Unlocking Personalized Healthcare on Modern CPUs/GPUs: Three-way Gene Interaction Study

Optimal algorithm for computing Steiner 3-eccentricities of trees

HeTM: Transactional Memory for Heterogeneous Systems

Counterexamples to conjectures on graph distance measures based on topological indexes

On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

A note on 'A New Approach To Compute Wiener Index'

Generalizations of Wiener polarity index and terminal Wiener index

Note on the harmonic index of a graph

Efficient algorithm for the vertex connectivity of trapezoid graphs

Laplacian Estrada index of trees

New results on the energy of integral circulant graphs

On Distance Spectral Radius and Distance Energy of Graphs

On Laplacian like energy of trees

On the extremal properties of the average eccentricity

On the Wiener index and Laplacian coefficients of graphs with given diameter or radius

On vertex covers and matching number of trapezoid graphs

The largest $n-1$ Hosoya indices of unicyclic graphs

See the researcher in context

Building this map preview

Aleksandar Ilic

Research overview

Is this your work?

17 publications

Unlocking Personalized Healthcare on Modern CPUs/GPUs: Three-way Gene Interaction Study

Optimal algorithm for computing Steiner 3-eccentricities of trees

HeTM: Transactional Memory for Heterogeneous Systems

Counterexamples to conjectures on graph distance measures based on topological indexes

On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

A note on 'A New Approach To Compute Wiener Index'

Generalizations of Wiener polarity index and terminal Wiener index

Note on the harmonic index of a graph

Efficient algorithm for the vertex connectivity of trapezoid graphs

Laplacian Estrada index of trees

New results on the energy of integral circulant graphs

On Distance Spectral Radius and Distance Energy of Graphs

On Laplacian like energy of trees

On the extremal properties of the average eccentricity

On the Wiener index and Laplacian coefficients of graphs with given diameter or radius

On vertex covers and matching number of trapezoid graphs

The largest n−1n-1n−1 Hosoya indices of unicyclic graphs

See the researcher in context

Building this map preview

The largest $n-1$ Hosoya indices of unicyclic graphs