Marcello Dalpasso
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Marcello Dalpasso has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Michele Favalli
University of Ferrara
19 shared publications - Piero Olivo
Dipartimento di Ingegneria, Universita degli Studi di Ferrara, Ferrara, Italy
10 shared publications B. Ricco
9 shared publications- Giuseppe Lancia
University of Udine
8 shared publications M. Favalli
5 shared publicationsP. Olivo
5 shared publications
Latest Publications
- Open Access
- 4 September 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (9) , 560
Speeding Up Floyd–Warshall’s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph
Floyd–Warshall’s algorithm is a widely-known procedure for computing all-pairs shortest paths in a graph of n vertices in time complexity. A simplified version of the same algorithm computes the transitive closure of the graph with the same time complexity. The algorithm operates on an matrix, performing n inspections and no more than n updates of each matrix cell, until the final matrix is computed. In this paper, we apply a technique called SmartForce, originally devised as a performance enhancement for solving the traveling salesman problem, to avoid the inspection and checking of cells that do not need to be updated, thus reducing the overall computation time when the number, u, of cell updates is substantially smaller than . When the ratio is not small enough, the performance of the proposed procedure might be worse than that of the Floyd–Warshall algorithm. To speed up the algorithm independently of the input instance type, we introduce an effective hybrid approach. Finally, a similar procedure, which exploits suitable fast data structures, can be used to achieve a speedup over the Floyd–Warshall simplified algorithm that computes the transitive closure of a graph.- 4 September 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (9) , 560
Open AccessSpeeding Up Floyd–Warshall’s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph
Floyd–Warshall’s algorithm is a widely-known procedure for computing all-pairs shortest paths in a graph of n vertices in time complexity. A simplified version of the same algorithm computes the transitive closure of the graph with the same time complexity. The algorithm operates on an matrix, performing n inspections and no more than n updates of each matrix cell, until the final matrix is computed. In this paper, we apply a technique called SmartForce, originally devised as a performance enhancement for solving the traveling salesman problem, to avoid the inspection and checking of cells that do not need to be updated, thus reducing the overall computation time when the number, u, of cell updates is substantially smaller than . When the ratio is not small enough, the performance of the proposed procedure might be worse than that of the Floyd–Warshall algorithm. To speed up the algorithm independently of the input instance type, we introduce an effective hybrid approach. Finally, a similar procedure, which exploits suitable fast data structures, can be used to achieve a speedup over the Floyd–Warshall simplified algorithm that computes the transitive closure of a graph. - Open Access
- 1 July 2025
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 25 (4) , 522-539
Fine-Grained Timing Analysis of Digital Integrated Circuits in Answer Set Programming
In the design of integrated circuits, one critical metric is the maximum delay introduced by combinational modules within the circuit. This delay is crucial because it represents the time required to perform a computation: in an Arithmetic Logic Unit, it represents the maximum time taken by the circuit to perform an arithmetic operation. When such a circuit is part of a larger, synchronous system, like a CPU, the maximum delay directly impacts the maximum clock frequency of the entire system. Typically, hardware designers use static timing analysis to compute an upper bound of the maximum delay because it can be determined in polynomial time. However, relying on this upper bound can lead to suboptimal processor speeds, thereby missing performance opportunities. In this work, we tackle the challenging task of computing the actual maximum delay, rather than an approximate value. Since the problem is computationally hard, we model it in answer set programming (ASP), a logic language featuring extremely efficient solvers. We propose non-trivial encodings of the problem into ASP. Experimental results show that ASP is a viable solution to address complex problems in hardware design.
- 1 July 2025
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 25 (4) , 522-539
Open AccessFine-Grained Timing Analysis of Digital Integrated Circuits in Answer Set Programming
In the design of integrated circuits, one critical metric is the maximum delay introduced by combinational modules within the circuit. This delay is crucial because it represents the time required to perform a computation: in an Arithmetic Logic Unit, it represents the maximum time taken by the circuit to perform an arithmetic operation. When such a circuit is part of a larger, synchronous system, like a CPU, the maximum delay directly impacts the maximum clock frequency of the entire system. Typically, hardware designers use static timing analysis to compute an upper bound of the maximum delay because it can be determined in polynomial time. However, relying on this upper bound can lead to suboptimal processor speeds, thereby missing performance opportunities. In this work, we tackle the challenging task of computing the actual maximum delay, rather than an approximate value. Since the problem is computationally hard, we model it in answer set programming (ASP), a logic language featuring extremely efficient solvers. We propose non-trivial encodings of the problem into ASP. Experimental results show that ASP is a viable solution to address complex problems in hardware design.
- Open Access
- 21 December 2023
- Published by Springer Nature in Journal of Heuristics
- Vol. 30 (3-4) , 109-144
Algorithmic strategies for a fast exploration of the TSP $4$-OPT neighborhoodWe describe an effective algorithm for exploring the $$4$$ -OPT neighborhood for the Traveling Salesman Problem. $$4$$ -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ algorithm by complete enumeration, but a $$\Theta (n^3)$$ dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ algorithm also exists for a particular subset of symmetric $$4$$ -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ -OPT move, and discuss the strength of the $$4$$ -OPT neighborhood compared to 2- and $$3$$ -OPT.- 21 December 2023
- Published by Springer Nature in Journal of Heuristics
- Vol. 30 (3-4) , 109-144
Open AccessAlgorithmic strategies for a fast exploration of the TSP $4$-OPT neighborhoodWe describe an effective algorithm for exploring the $$4$$ -OPT neighborhood for the Traveling Salesman Problem. $$4$$ -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ algorithm by complete enumeration, but a $$\Theta (n^3)$$ dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ algorithm also exists for a particular subset of symmetric $$4$$ -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ -OPT move, and discuss the strength of the $$4$$ -OPT neighborhood compared to 2- and $$3$$ -OPT. - Open Access
- 27 January 2022
- Published by MDPI AG in Electronics
- Vol. 11 (3) , 382
Techniques for SAT-Based Boolean Reasoning on Multiple Faults Affecting Logic Cells and Interconnects in Digital ICs
We propose a new method for SAT-based Boolean reasoning on multiple defects in digital ICs. Although it does not explicitly consider a specific fault model such as model-based techniques, it allows us to consider more realistic cases than model-free approaches. In particular, it can be used to account for (a) faults resulting in monotonic errors at the output of a cell and (b) faults, such as breaks or bridgings, that may corrupt the propagation of a signal from its fan-out branches. The model can be used for either standard gates or more complex combinational modules. Examples are shown for applications requiring the consideration of multiple defects such as fault diagnosis and reliability analysis. The feasibility of the proposed approach is assessed by results on a set of combinational benchmarks.
- 27 January 2022
- Published by MDPI AG in Electronics
- Vol. 11 (3) , 382
Open AccessTechniques for SAT-Based Boolean Reasoning on Multiple Faults Affecting Logic Cells and Interconnects in Digital ICs
We propose a new method for SAT-based Boolean reasoning on multiple defects in digital ICs. Although it does not explicitly consider a specific fault model such as model-based techniques, it allows us to consider more realistic cases than model-free approaches. In particular, it can be used to account for (a) faults resulting in monotonic errors at the output of a cell and (b) faults, such as breaks or bridgings, that may corrupt the propagation of a signal from its fan-out branches. The model can be used for either standard gates or more complex combinational modules. Examples are shown for applications requiring the consideration of multiple defects such as fault diagnosis and reliability analysis. The feasibility of the proposed approach is assessed by results on a set of combinational benchmarks.
- Open Access
- 23 November 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (11) , 306
Finding the Best 3-OPT Move in Subcubic Time
Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the enumeration of all triples is likely to exist for this problem, but algorithms with average case are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by ) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances.- 23 November 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (11) , 306
Open AccessFinding the Best 3-OPT Move in Subcubic Time
Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the enumeration of all triples is likely to exist for this problem, but algorithms with average case are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by ) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances. - Open Access
- 1 May 2019
- Published by MDPI AG in Algorithms
- Vol. 12 (5) , 91
FASTSET: A Fast Data Structure for the Representation of Sets of Integers
We describe a simple data structure for storing subsets of , with N a given integer, which has optimal time performance for all the main set operations, whereas previous data structures are non-optimal for at least one such operation. We report on the comparison of a Java implementation of our structure with other structures of the standard Java Collections.- 1 May 2019
- Published by MDPI AG in Algorithms
- Vol. 12 (5) , 91
Open AccessFASTSET: A Fast Data Structure for the Representation of Sets of Integers
We describe a simple data structure for storing subsets of , with N a given integer, which has optimal time performance for all the main set operations, whereas previous data structures are non-optimal for at least one such operation. We report on the comparison of a Java implementation of our structure with other structures of the standard Java Collections. - 30 December 2018
- Published by Springer Nature
- p. 345-355
Speeding-up the Exploration of the $3$-OPT Neighborhood for the TSP- 30 December 2018
- Published by Springer Nature
- p. 345-355
Speeding-up the Exploration of the $3$-OPT Neighborhood for the TSP- 7 August 2018
- Published by Springer Nature
- p. 105-114
New Modeling Ideas for the Exact Solution of the Closest String Problem
- 7 August 2018
- Published by Springer Nature
- p. 105-114
New Modeling Ideas for the Exact Solution of the Closest String Problem
- 17 September 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (3) , 706-715
Boolean and Pseudo-Boolean Test Generation for Feedback Bridging Faults
Feedback bridging faults may give rise to oscillations within integrated circuits. This work mainly investigates the propagation of oscillations, a behavior that may have a relevant impact on the fault detection. We propose both a logic-level model of the faulty circuit and two techniques aiming to the generation of high-quality test sequences.
- 17 September 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (3) , 706-715
Boolean and Pseudo-Boolean Test Generation for Feedback Bridging Faults
Feedback bridging faults may give rise to oscillations within integrated circuits. This work mainly investigates the propagation of oscillations, a behavior that may have a relevant impact on the fault detection. We propose both a logic-level model of the faulty circuit and two techniques aiming to the generation of high-quality test sequences.