The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, it has been employed ...to solve a considerable number of optimization problems; however, it has never been explored as a solver for graph labeling problems. Hence, in this paper, we contribute to bridging this gap by proposing a population-based iterated greedy to solve the S-labeling problem. The construction phase invokes a novel greedy algorithm for the problem and the destruction phase engages a destructive strength that is attenuated as the algorithm progresses. In addition, it incorporates a restart operator that is activated according to an innovative criterion for detecting convergence. Extensive experiments verify that the proposal can achieve better solution quality than the state-of-the-art optimizer for this optimization problem and other competing algorithms. We have completed the study about the potential of the iterated greedy metaheuristic for graph labeling problems by evaluating experimentally the performance of an extension of the proposed algorithm that solves the Antibandwidth problem. Remarkably, it provides comparable results to those of the best algorithms in the literature for this complex case of labeling problem.
•A population-based iterated greedy (PIG) for solving the S-labeling problem is introduced.•PIG ensures an intensification/diversification balance by using specialized operators.•It was able to outperform the state-of-the-art method in all the tested instances.•PIG was also adapted to tackle the antibandwidth problem showing remarkable results.
The Cyclic Bandwidth Problem is an important graph labeling problem with numerous applications. This work aims to advance the state-of-the-art of practically solving this computationally challenging ...problem. We present an effective heuristic algorithm based on the general iterated local search framework and integrating dedicated search components. Specifically, the algorithm relies on a simple, yet powerful local optimization procedure reinforced by two complementary perturbation strategies. The local optimization procedure discovers high-quality solutions in a particular search zone while the perturbation strategies help the search to escape local optimum traps and explore unvisited areas. We present intensive computational results on 113 benchmark instances from 8 different families, and show performances that are never achieved by current best algorithms in the literature.
k-ZUMKELLER LABELING OF CERTAIN GRAPHS Mishra, Arijit
JOURNAL OF MECHANICS OF CONTINUA AND MATHEMATICAL SCIENCES,
04/2024, Volume:
19, Issue:
4
Journal Article
Peer reviewed
Open access
Let G be any graph. Then a one-one function f:V→ N is said to be a k-Zumkeller labeling of G if the induced function f^*: E→N defined by f^* (xy) =f(x)f(y) satisfies the following conditions: (i) For ...every xy∈E, f^* (xy) is a Zumkeller number. (ii) |f^* (E)|=k, where |f^* (E)| denotes the number of distinct Zumkeller numbers on the edges of G. In this paper, we prove the existence of k-Zumkeller labeling for certain graphs like tadpole, banana, friendship, and firecracker graphs.
Focus+Context Metro Maps Wang, Yu-Shuen; Chi, Ming-Te
IEEE transactions on visualization and computer graphics
17, Issue:
12
Journal Article
Peer reviewed
We introduce a focus+context method to visualize a complicated metro map of a modern city on a small displaying area. The context of our work is with regard the popularity of mobile devices. The best ...route to the destination, which can be obtained from the arrival time of trains, is highlighted. The stations on the route enjoy larger spaces, whereas the other stations are rendered smaller and closer to fit the whole map into a screen. To simplify the navigation and route planning for visitors, we formulate various map characteristics such as octilinear transportation lines and regular station distances into energy terms. We then solve for the optimal layout in a least squares sense. In addition, we label the names of stations that are on the route of a passenger according to human preferences, occlusions, and consistencies of label positions using the graph cuts method. Our system achieves real-time performance by being able to report instant information because of the carefully designed energy terms. We apply our method to layout a number of metro maps and show the results and timing statistics to demonstrate the feasibility of our technique.
Graceful game on some graph classes de Oliveira, Deise L.; Artigas, Danilo; Dantas, Simone ...
R.A.I.R.O. Recherche opérationnelle,
01/2024, Volume:
58, Issue:
1
Journal Article
Peer reviewed
Open access
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.
Divisor Labeling of Some Special Graphs Parthiban, A.; Samdanielthompson, G.; Sharma, Deepak
Journal of physics. Conference series,
05/2020, Volume:
1531, Issue:
1
Journal Article
Peer reviewed
Open access
An assignment of labels (mostly, integers) to the vertices of a graph G(V,E), or simply G, on n vertices subject to certain constraints is called a vertex labeling of G. A graph G is a divisor graph ...if the vertices of G can be labeled with integers (necessarily distinct) in such a way that either x|y or y|x for any two adjacent vertices x and y. In this paper, we encounter the divisor labeling of certain classes of graphs.
On regular handicap graphs of even order Fronček, Dalibor; Kovář, Petr; Kovářová, Tereza ...
Electronic notes in discrete mathematics,
July 2017, 2017-07-00, Volume:
60
Journal Article
Let G=(V,E) be a simple graph of order n. A bijection f : V→{1,2,…,n} is a handicap labeling of G if there exists an integer ℓ such that ∑u∈N(v)f(u)=ℓ+f(v) for all v∈V, where N(v) is the set of all ...vertices adjacent to v. Any graph which admits a handicap labeling is a handicap graph.
We present an overview of results, which completely answer the question of existence of regular handicap graphs of even order.
Most modern approaches for video-based multiple people tracking rely on human appearance to exploit similarities between person detections. Consequently, tracking accuracy degrades if this kind of ...information is not discriminative or if people change apparel. In contrast, we present a method to fuse video information with additional motion signals from body-worn inertial measurement units (IMUs). In particular, we propose a neural network to relate person detections with IMU orientations, and formulate a graph labeling problem to obtain a tracking solution that is globally consistent with the video and inertial recordings. The fusion of visual and inertial cues provides several advantages. The association of detection boxes in the video and IMU devices is based on motion, which is independent of a person's outward appearance. Furthermore, inertial sensors provide motion information irrespective of visual occlusions. Hence, once detections in the video are associated with an IMU device, intermediate positions can be reconstructed from corresponding inertial sensor data, which would be unstable using video only. Since no dataset exists for this new setting, we release a dataset of challenging tracking sequences, containing video and IMU recordings together with ground-truth annotations. We evaluate our approach on our new dataset, achieving an average IDF1 score of 91.2%. The proposed method is applicable to any situation that allows one to equip people with inertial sensors.
We investigate the modular edge-gracefulness k(G) of a graph, i.e., the least integer k such that taking a cyclic group Zk of order k, there exists a function f:E(G)→Zk so that the sums of edge ...labels incident with every vertex are distinct. So far the best upper bound on k(G) for a general graph G is 2n, where n is the order of G. In this note we prove that if G is a graph of order n without star as a component then k(G)=n for n¬≡2(mod4) and k(G)=n+1 otherwise. Moreover we show that for such G for every integer t≥k(G) there exists a Zt-irregular labeling.
Inspired by distance-constrained graph labelings that model the assignment of frequencies to transmitters, we introduce a distance-constrained labeling of connected graphs that models the assignment ...of frequencies to oscillators. For a graph G and a vector of nonnegative real numbers k=(k1,k2,…,kp), an L∗(G;k)-labeling is any function f from V(G) into R such that for each i,1≤i≤p, |f(v)−f(w)|≤ki if d(v,w)=i. The span of f is the absolute difference between the supremum and infimum of the image of f, and λG,k∗ is the maximum span over all L∗(G,k) labelings. In this paper, we explore the properties of λG,k∗ as a function of k, including continuity. And, for p=2, we establish λG,k∗ when G is either a tree or a cycle.
PDF
