Author name cluster

Michele Zito

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

I&C Journal 2020 Journal Article

Dynamic programming optimization in line of sight networks

Pavan Sangha
Prudence W.H. Wong
Michele Zito

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles. For fixed positive integer d, and positive integer ω, a graph G = ( V, E ) is a (d-dimensional) LoS network with range parameter ω if it can be embedded in a finite cube of the d-dimensional integer grid so that each pair of vertices in V are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than ω. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally, for any ω, on narrow LoS networks (i. e. networks which can be embedded in a k × k … × k × n region, for some fixed k independent of n). In the unrestricted case it has been shown that the (decision version of the) problem is NP-hard when 2 < ω = O ( n 1 − δ ), for fixed 0 < δ < 1. We describe how DP can be used as a building block in the design of good approximation algorithms in this case. In particular we present a semi-online polynomial-time approximation scheme for the MIS problem in narrow d-dimensional LoS networks, as well as a polynomial-time 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary d-dimensional LoS networks. Finally we comment on how the approach can be adapted to prove similar results for a number of important optimization problems in LoS networks.

Details DOI

KER Journal 2012 Journal Article

A survey of frequent subgraph mining algorithms

Chuntao Jiang
Frans Coenen
Michele Zito

Abstract Graph mining is an important research area within the domain of data mining. The field of study concentrates on the identification of frequent subgraphs within graph data sets. The research goals are directed at: (i) effective mechanisms for generating candidate subgraphs (without generating duplicates) and (ii) how best to process the generated candidate subgraphs so as to identify the desired frequent subgraphs in a way that is computationally efficient and procedurally effective. This paper presents a survey of current research in the field of frequent subgraph mining and proposes solutions to address the main research issues.

Details DOI

TCS Journal 2009 Journal Article

Large independent sets in random regular graphs

William Duckworth
Michele Zito

We present algorithmic lower bounds on the size s d of the largest independent sets of vertices in random d -regular graphs, for each fixed d ≥ 3. For instance, for d = 3 we prove that, for graphs on n vertices, s d ≥ 0. 43475 n with probability approaching one as n tends to infinity.

Details DOI

TCS Journal 2003 Journal Article

On polynomial-time approximation algorithms for the variable length scheduling problem

Artur Czumaj
Leszek Ga̧sieniec
Daya Ram Gaur
Ramesh Krishnamurti
Wojciech Rytter
Michele Zito

This paper may be viewed as a corrigendum as well as an extension of the paper by (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582) where they deal with the variable length scheduling problem (VLSP) with parameters k 1, k 2, denoted VLSP(k 1, k 2). In the current paper, we first discuss an error in the analysis of one of the approximation algorithms described in (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582), where an approximation algorithm for VLSP(k 1, k 2), k 1<k 2, was presented and it was claimed that the algorithm achieves the approximation ratio of 1+(k 1(k 2−k 1))/k 2. In this paper we give a problem instance for which the same algorithm obtains the approximation ratio ≈ k2 k1. We then present two simple approximation algorithms, one for the case k1 =1 with an approximation ratio of 2, and one for the case k 1>1 with an approximation ratio of 2+(k 2/2k 1). This corrects the result claimed in (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582).

Details DOI

TCS Journal 2003 Journal Article

Small maximal matchings in random graphs

Michele Zito

We look at the minimal size of a maximal matching in general, bipartite and d-regular random graphs. We prove that with high probability the ratio between the sizes of any two maximal matchings approaches one in dense random graphs and random bipartite graphs. Weaker bounds hold for sparse random graphs and random d-regular graphs. We also describe an algorithm that with high probability finds a matching of size strictly less than n/2 in a cubic graph. The result is based on approximating the algorithm dynamics by a number of systems of linear differential equations.

Details DOI

TCS Journal 2001 Journal Article

Efficient web searching using temporal factors

Artur Czumaj
Ian Finch
Leszek Ga̧sieniec
Alan Gibbons
PAUL LENG
Wojciech Rytter
Michele Zito

We study the issues involved in the design of algorithms for performing information gathering more efficiently, by taking advantage of anticipated variations in access times in different regions at different times of the day or week. We look at the problem theoretically, as a generalisation of single processor sequencing with release times and deadlines, in which performance times (lengths) of the tasks can change in time. The new problem is called Variable Length Sequencing Problem (VLSP). We show that although the decision version of VLSP seems to be intractable in the general case, it can be solved optimally for lengths 1 and 2. This result opens the possibility of practicable algorithms to schedule searches efficiently when expected access times can be categorised as either slow or fast. Some algorithms for more general cases are examined and complexity results derived.

Details DOI

TCS Journal 2000 Journal Article

Complexity-theoretic models of phase transitions in search problems

Paul E. Dunne
Alan Gibbons
Michele Zito

In recent years, numerous studies have observed that many hard combinatorial decision problems exhibit behaviour described as a ‘phase-transition’. This is the phenomenon whereby typical instances of a problem display a dramatic shift in certain characteristics as some parameter of the instances is varied. Such characteristics include the likelihood of an instance having a solution and the time taken by a search algorithm. The apparent pervasiveness of phase-transitions in hard combinatorial search problems has led to contrasting claims being advanced concerning to what extent all NP-complete problems exhibit phase-transitions. The established importance of exploiting phase-transition effects in the design of search heuristics provides a strong motivation for assessing how valid such claims may be. In this paper we argue that questions concerning the generality of phase-transition phenomena are, at present, ill-defined. In order to address this difficulty, we propose and examine rigorous complexity-theoretic models of the statement ‘the decision problem D has a phase-transition’. Within these models it is proved that for certain ‘natural’ definitions contrasting results about phase-transition behaviour can be proved.

Details DOI