ON THE EDGE-SUM DISTINGUISHING GAME Deise L. de Oliveira, Danilo Artigas, Simone Dantas, Atílio G. Luiz Discussiones Mathematicae Graph Theory, 2024
GRACEFUL GAME ON SOME GRAPH CLASSES Deise L. de Oliveira, Danilo Artigas, Simone Dantas, Luisa Frickes, Atílio G. Luiz RAIRO Operations Research, 2024 A graceful labeling of a graph G with m edges consists in labeling the vertices of G with distinct integers from 0 to m such that each edge is uniquely identified by the absolute difference of the labels of its endpoints. In this work, we study the graceful labeling problem in the context of maker-breaker graph games. The Graceful Game was introduced by Tuza, in 2017, as a two-players game on a connected graph in which the players, Alice and Bob, take moves labeling the vertices with distinct integers from 0 to m. Players are constrained to use only legal labelings (moves), that is, after a move, all edge labels are distinct. Alice’s goal is to obtain a graceful labeling for the graph, as Bob’s goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in graph classes: paths, complete graphs, cycles, complete bipartite graphs, caterpillars, trees, gear graphs, web graphs, prisms, hypercubes, 2-powers of paths, wheels and fan graphs.
Task Scheduling for Subsea Flexible Pipes Decommissioning Robert da Silva Bressan, Danilo Artigas Proceedings of the Annual Offshore Technology Conference, 2021 Subsea flexible pipelines removal is subject to order restrictions, mostly caused by crossings. It is proposed to create a computational algorithm to design an optimal order of vessel intervention over a field. A real field was studied, and, from it, the mathematical base model was created upon graph theory, with great correlation with the minimum feedback arc set problem. Vessel movements were discretized and reduced to removal, reposition, and cut, leading to a state search. A-star algorithm was implemented to guide the search for the solution. Then, the complete algorithm was built, tested in a minimal environment, and finally applied to the real instance. To improve performance, a beam search filtering was envisioned, using seven ranking functions. Constructed model is suspected to be NP-hard, by correlation to minimum feedback arc set problem, leading to a large space search. Instances containing under 100 crossings were solved optimally, without needing any assistance. After implementing the heuristics and beam search, solution time was lowered by about 20 times, demonstrating the effectiveness of the technique. Also, ranking functions for pipe repositioning based on crossing count led to better results than crossing density. For cutting, an approximation based on feedback arc set was used. GreedyFAS was employed and gave satisfactory results. Bigger instances containing around 3000 crossings could not be solved optimally in a reasonable time, even with the heuristics. Improvements in A-star estimation function and bound the solution branches might lead to an optimal solution for these larger instances. Model proposed simplifies the operational order decisions and helps build the scheduling of operations. As it is based on state search, other aspects in logistics, vessel capacities and steps in decommissioning processes may be added, adjusting the neighboring weights and branching, keeping the same core.
Computational and structural analysis of the contour of graphs Danilo Artigas, Simone Dantas, Alonso L. S. Oliveira, Thiago M. D. Silva International Transactions in Operational Research, 2018 Let be a finite, simple, and connected graph. The closed interval of a set is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if . The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour of G is the set formed by the contour vertices of G. We consider two problems: the problem of determining whether the contour of a graph class is geodetic; the problem of determining if there exists a graph such that is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem and show two infinite families such that is not geodetic. Using computational tools, we establish the minimum graphs for which is not geodetic; and show that all graphs with , and all bipartite graphs with , are such that is geodetic.
Can we trust the health information we find online? Identification of influential nodes Leila Weitzel, Paulo Quaresma, Jose Palazzo Moreira de Oliveira, Danilo Artigas Graph Theoretic Approaches for Analyzing Large Scale Social Networks, 2017 The Internet is becoming increasingly an important source of information for people who are seeking healthcare information. Users do so without professional guidance and may lack sufficient knowledge and training to evaluate the validity and quality of health web content. This is particularly problematic in the era of Web 2.0. Hence, the main goal of this research is to propose an approach to infer user reputation based on social interactions. Reputation is a social evaluation towards a person or a group of people. The results show that our rank methodology and the network topology succeeded in achieving user reputation. The results also show that centrality measures associated with the weighted ties approach suitably controls suitably the ranking of nodes.
