Variable neighborhood search with ejection chains for the antibandwidth problem

In this paper, we address the optimization problem arising in some practical applications in which we want to maximize the minimum difference between the labels of adjacent elements. For example, in the context of location models, the elements can represent sensitive facilities or chemicals and their labels locations, and the objective is to locate (label) them in a way that avoids placing some of them too close together (since it can be risky). This optimization problem is referred to as the antibandwidth maximization problem (AMP) and, modeled in terms of graphs, consists of labeling the vertices with different integers or labels such that the minimum difference between the labels of adjacent vertices is maximized. This optimization problem is the dual of the well-known bandwidth problem and it is also known as the separation problem or directly as the dual bandwidth problem. In this paper, we first review the previous methods for the AMP and then propose a heuristic algorithm based on the variable neighborhood search methodology to obtain high quality solutions. One of our neighborhoods implements ejection chains which have been successfully applied in the context of tabu search. Our extensive experimentation with 236 previously reported instances shows that the proposed procedure outperforms existing methods in terms of solution quality.     

Stack-up algorithms for palletizing at delivery industry

We study the following multi-objective combinatorial stack-up problem from delivery industry. Given a sequence q of labeled bins and two positive integers s and p. The aim is to stack-up the bins by iteratively removing one of the first s bins of the sequence and put it to one of p stack-up places. Each of these places has to contain bins of only one label, bins of different labels have to be placed on different places. If all bins of a label are removed from q, the corresponding place becomes available for bins of another label. We analyze the worst-case performance of simple algorithms for the stack-up problem that are very interesting from a practical point of view. In particular, we show that the so-called Most-Frequently on-line algorithm is (2,2)-competitive and has optimal worst-case on-line performance.     

Face Antimagic Labeling of Jahangir Graph

This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a super d-antimagic labeling the vertices receive the smallest labels and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s that appearing in the graph. The paper examines the existence of super d-antimagic labelings for Jahangir graphs for certain differences d.     

Rank numbers of grid graphs

A ranking of a graph is a labeling of the vertices with positive integers such that any path between vertices of the same label contains a vertex of greater label. The rank number of a graph is the smallest possible number of labels in a ranking. We find rank numbers of the Möbius ladder, K_s×P_n, and P₃×P_n. We also find bounds for rank numbers of general grid graphs P_m×P_n.     

POPMUSIC for the point feature label placement problem

Point feature label placement is the problem of placing text labels adjacent to point features on a map so as to maximize legibility. The goal is to choose positions for the labels that do not give rise to label overlaps and that minimize obscuration of features. A practical goal is to minimize the number of overlaps while considering cartographic preferences. This article proposes a new heuristic for solving the point feature label placement problem based on the application of the POPMUSIC frame. Computational experiments show that the proposed heuristic outperformed other recent metaheuristics approaches in the literature. Experiments with problem instances involving up to 10 million points show that the computational time of the proposed heuristic increases almost linearly with the problem size. New problem instances based on real data with more than 13,000 labels are proposed.     

Global optimization for first order Markov Random Fields with submodular priors

This paper copes with the global optimization of Markovian energies. Energies are defined on an arbitrary graph and pairwise interactions are considered. The label set is assumed to be linearly ordered and of finite cardinality, while each interaction term (prior) shall be a submodular function. We propose an algorithm that computes a global optimizer under these assumptions. The approach consists of mapping the original problem into a combinatorial one that is shown to be globally solvable using a maximum-flow/s-t minimum-cut algorithm. This restatement relies on considering the level sets of the labels (seen as binary variables) instead of the label values themselves. The submodularity assumption of the priors is shown to be a necessary and sufficient condition for the applicability of the proposed approach. Finally, some numerical results are presented.     

Super Face Antimagic Labelings of Union of Antiprisms

In this paper we deal with the problem of labeling the vertices, edges and faces of a disjoint union of m copies of antiprism by the consecutive integers starting from 1 in such a way that the set of face-weights of all s-sided faces forms an arithmetic progression with common difference d, where by the face-weight we mean the sum of the label of that face and the labels of vertices and edges surrounding that face. Such a labeling is called super if the smallest possible labels appear on the vertices. The paper examines the existence of such labelings for union of antiprisms for several values of the difference d.     

On the asymmetric representatives formulation for the vertex coloring problem

We consider the vertex coloring problem, which can be stated as the problem of minimizing the number of labels that can be assigned to the vertices of a graph G such that each vertex receives at least one label and the endpoints of every edge are assigned different labels. In this work, the 0-1 integer programming formulation based on representative vertices is revisited to remove symmetry. The previous polyhedral study related to the original formulation is adapted and generalized. New versions of facets derived from substructures of G are presented, including cliques, odd holes and anti-holes and wheels. In addition, a new class of facets is derived from independent sets of G. Finally, a comparison with the independent sets formulation is provided.     

Antibandwidth of three-dimensional meshes

The antibandwidth problem is to label vertices of a graph G=(V,E) bijectively by 0,1,2,…,|V|−1 so that the minimal difference of labels of adjacent vertices is maximised. In this paper we prove an almost exact result for the antibandwidth of three-dimensional meshes. Provided results are extensions of the two-dimensional case and an analogue of the result for the bandwidth of three-dimensional meshes obtained by FitzGerald.     

Optimal labeling of point features in rectangular labeling models

 We investigate the NP–hard label number maximization problem (LNM): Given a set of rectangular labels Λ, each of which belongs to a point feature in the plane, the task is to find a labeling for a largest subset Λ _P of Λ. A labeling is a placement such that none of the labels overlap and each λΛ _P is placed according to a labeling model: In the discrete models, the label must be placed so that the labeled point coincides with an element of a predefined subset of corners of the rectangular label, in the continuous or slider models, the point must lie on a subset of boundaries of the label. Obviously, the slider models allow a continuous movement of a label around its point feature, leading to a significantly higher number of labels that can be placed. We present exact algorithms for this problem that are based on a pair of so-called constraint graphs that code horizontal and vertical positioning relations. The key idea is to link the two graphs by a set of additional constraints, thus characterizing all feasible solutions of LNM. This enables us to formulate a zero-one integer linear program whose solution leads to an optimal labeling. We can express LNM in both the discrete and the slider labeling models. To our knowledge, we present the first algorithm that computes provably optimal solutions in the slider models. We find it remarkable that our approach is independent of the labeling model and results in a discrete algorithm even if the problem is of continuous nature as in the slider models. Extensive experimental results on both real-world instances and point sets created by a widely used benchmark generator show that the new approach - although being an exponential time algorithm - is applicable in practice. Received: November 20, 2000 / Accepted: April 9, 2002 Published online: September 5, 2002 RID="★" ID="★" This work is partially supported by the German Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie (No. 03-MU7MP1-4). Key words. map labeling – point feature map labeling – constraint graphs – combinatorial optimization – integer programming     

Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

Total Edge Irregularity Strength of Toroidal Fullerene

A toroidal fullerene (toroidal polyhex) is a cubic bipartite graph embedded on the torus such that each face is a hexagon. An edge irregular total k-labeling of a graph G is such a labeling of the vertices and edges with labels 1, 2, … , k that the weights of any two different edges are distinct, where the weight of an edge is the sum of the label of the edge itself and the labels of its two endvertices. The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength, tes(G). In this paper we determine the exact value of the total edge irregularity strength of toroidal polyhexes.     

A note on the partitioning shortest path algorithm

Recently Glover, Klingman and Phillips proposed the Partitioning Shortest Path (PSP) algorithm. The PSP algorithm includes as variants most of the known algorithms for the shortest path problem. In a subsequent paper, together with Schneider, they proposed several variants of the PSP and conducted computational tests. Three of the variants were the first polynomially bounded shortest path algoriths to maintain sharp labels as defined by Shier and Witzgall. Two of these variants had computational complexity O(|N|²|A|), the other O(|N|³). In this note, we add a new step to the PSP algorithm resulting in new variants also scanning from sharp labels and having computational complexity O(|N|³) for two of them and O(|N|²) for the other. This new step also provides a test for the early detection of negative length cycles.     

Minimum Eulerian circuits and minimum de Bruijn sequences

Given a digraph (directed graph) with a labeling on its arcs, we study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label.     

Face labelings of Klein-bottle fullerenes

The Klein-bottle fullerene is a finite trivalent graph embedded on the Klein-bottle such that each face is a hexagon. The paper deals with the problem of labeling the vertices, edges and faces of the Klein-bottle fullerene in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face and the weights of all 6-sided faces constitute an arithmetic progression of difference d. In this paper we study the existence of such labelings for several differences d.     

Labelings of plane graphs containing Hamilton path

This paper deals with the problem of labeling the vertices, edges and faces of a plane graph. A weight of a face is the sum of the label of a face and the labels of the vertices and edges surrounding that face. In a super d-antimagic labeling the vertices receive the smallest labels and the weights of all s-sided faces constitute an arithmetic progression of difference d, for each s appearing in the graph.     

The spum and sum-diameter of graphs: Labelings of sum graphs

A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph G is the minimum difference between the largest and smallest labels in a sum graph consisting of G and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.     

Localized and compact data-structure for comparability graphs

We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n^1/3) bit labels.     

Sperner labellings: A combinatorial approach

In 2002, De Loera, Peterson and Su proved the following conjecture of Atanassov: let T be a triangulation of a d-dimensional polytope P with n vertices v₁,v₂,…,vn; label the vertices of T by 1,2,…,n in such a way that a vertex of T belonging to the interior of a face F of P can only be labelled by j if vj is on F; then there are at least n−d simplices labelled with d+1 different labels. We prove a generalisation of this theorem which refines this lower bound and which is valid for a larger class of objects.