Let be a connected undirected graph, a set of nodes, a set of edges, , and . Given a non‐negative weight function associated with its edges, a set of terminal sets , the Steiner forest problem (SFP) consists of finding a subset of edges with the minimal cost such that all vertices of each (for ) lie in the same connected component in the graph induced by . In this work, as a first contribution, we propose a constructive algorithm for the SFP. Computational experiments on literature instances showed that the results obtained by the constructive algorithm outperformed the state‐of‐the‐art primal‐dual algorithm. Furthermore, as a second contribution, we present two heuristics to solve the SFP: the first, named GRASP‐SFP, based on the GRASP metaheuristic, and the second, called MDM‐GRASP‐SFP, which incorporates a data mining component on GRASP‐SFP. In most test instances provided in the literature, the results obtained by the two proposed algorithms tied for both best and average solution costs. Due to this fact, we generated more challenging SFP instances and the results reached by the proposed hybrid data mining heuristic improved upon those obtained by the original GRASP approach.
Murilo Stockinger, Isabel Rosseti, Simone Martins et al.· International Transactions i...· 0 citations
Modern software development involves parallel work and concurrent changes, requiring code merging. Prior studies report that 10% to 20% of merge attempts result in conflicts, often requiring manual intervention. The literature explores factors that generate conflicts, including refactorings, but does not analyze how individual refactoring types influence the manual effort required to resolve them. We analyzed 64 open-source Java projects and applied association rule mining to measure the strength of associations between specific refactoring types and merge effort. Our results show that refactoring types relate to merge effort with varying strength. In particular, Rename Attribute, Move Class, Extract Variable, Change Return Type, and Split Parameter exhibit some of the strongest associations, especially when a higher number of such refactorings is present in the merge branches. We also find that both the number of refactorings and their diversity independently increase merge effort, both in terms of occurrence and intensity. Additionally, the co-occurrence of refactorings across parallel branches is associated with higher merge effort, particularly when combining structural transformations with changes to method signatures and data-structure representations, whereas more localized changes are less frequent in the most impactful combinations.
A. Oliveira, João Victor Monteiro, V. Neves et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
