The current study develops a new general heuristic approach to address a special class of combinatorial problems, efficiently. The approach combines discrete event simulation together with relaxation ...techniques to solve a special class of 0-1 programming models including a constraint that restricts the summation of all variables to be 1. Three well-known combinatorial problems -including such a constraint- such as Dynamic Facility Layout Problem (DFLP), Graph Labelling Problem (GLP) and Travelling Salesman Problem (TSP) have been addressed and could be solved efficiently by the proposed algorithm. Several experiments have been carried out to show the efficiency of the algorithm. The results show that the proposed algorithm can be used for several real world applications while according to the best knowledge of the author, at least for DFLP and GLP, it is the fastest algorithm which has been developed in the literature.
Blockchain uses a large number of cryptographic algorithms to ensure security. We will construct multiple topological authentications by topological graphic passwords and Topsnut-matchings, since ...matchings' phenomenon appear in almost branches of mathematics. We present two new techniques for our works, and design three construction algorithms for building up our multiple topological authentications. Our algorithms are based on graph labellings and graph operations. We give detail examples for illustrating each construction algorithm, and distribute a matching of two multiple topological authentication sets for producing text-based passwords with million or billion bytes in order to use them in quantum computer age.
The security of real networks is facing serious challenges and is harder than ever. We propose an idea of "topological structure + number theory" for designing new passwords. By means of graph theory ...we define a twin odd-graceful tree T = T 1 o T 2 obtained by identifying a certain vertex of T 1 with a certain vertex of T 2 together. We prove that some particular trees (key-models) can have their associated trees (lock-models) under the concept of twin odd-graceful trees. Trees having set-ordered odd-graceful labellings T 1 with their associated trees T 2 can produce certain twin odd-graceful trees such that these twin odd-graceful trees are odd-graceful.
Vertex Magic Total Labelings of Complete Graphs Krishnappa, H.K.; Kothapalli, Kishore; Venkaiah, V.Ch
AKCE international journal of graphs and combinatorics,
04/2009, Letnik:
6, Številka:
1
Journal Article
Recenzirano
A vertex magic total labeling of a graph G = (V, E) is a bijection f: V ≼ E → {1, 2,..., |V| + |E|} such that for every vertex w, the sum
is a constant. It is well known that all complete graphs K
n
...admit a vertex magic total labeling. In this paper we present a new proof of this theorem using the concepts of twin factorization and magic square.
This paper studies the polytope of the minimum‐span graph labelling problems with integer distance constraints (DC‐MSGL). We first introduce a few classes of new valid inequalities for the DC‐MSGL ...defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch‐and‐cut algorithm for solving the DC‐MSGL. Following that, we present our polyhedral results on the dimension of the DC‐MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC‐MSGL on triangular graphs.
Given a graph
G=(V,E), a
labelling is a function
f
:
V→Z
+
which has different values on different vertices of
G. Graph
G is a
sum graph if there exists a labelling
f
:
V→Z
+
such that for every pair ...of distinct vertices
u,v∈V, there is an edge
uv∈E if and only if there exists a vertex
w∈V with
f(w)=f(u)+f(v). It is clear that every sum graph has at least one isolated vertex. The
sum number
σ(G) of the graph
G is the least number of isolated vertices one must add to
G to turn it into a sum graph.
It was stated by Hartsfield and Smyth (in: R. Rees (Ed.), Graphs, Matrices and Designs, Marcel Dekker, New York, 1993, pp. 205) that for the complete bipartite graphs
K
m,n
where
m⩾n⩾2 the sum number is
σ(K
m,n)=⌈(3n+m−3)/2⌉
. Unfortunately, this formula is wrong when
m⩾3n. The new construction given in this paper shows that
σ(K
m,n)
in this case is much smaller. The new formula for
σ(K
m,n)
is proved.
Sparse matrices emerge in a number of problems in science and engineering. Typically the efficiency of solvers for such problems depends crucially on the distances between the first non-zero element ...in each row and the main diagonal of the problem’s matrix — a property assessed by a quantity called the size of the envelope of the matrix. This depends on the ordering of the variables (i.e., the order of the rows and columns in the matrix). So, some permutations of the variables may reduce the envelope size which in turn makes a problem easier to solve. However, finding the permutation that minimises the envelope size is an NP-complete problem. In this paper, we introduce a hyper-heuristic approach based on genetic programming for evolving envelope reduction algorithms. We evaluate the best of such evolved algorithms on a large set of standard benchmarks against two state-of-the-art algorithms from the literature and the best algorithm produced by a modified version of a previous hyper-heuristic introduced for a related problem. The new algorithm outperforms these methods by a wide margin, and it is also extremely efficient.
The bandwidth of a sparse matrix is the distance from the main diagonal beyond which all elements of the matrix are zero. The bandwidth minimisation problem for a matrix consists of finding the ...permutation of rows and columns of the matrix which ensures that the non-zero elements are located in as narrow a band as possible along the main diagonal. This problem, which is known to be NP-complete, can also be formulated as a vertex labelling problem for a graph whose edges represent the non-zero elements of the matrix. In this paper, a Genetic Programming approach is proposed and tested against two of the best-known and widely used bandwidth reduction algorithms. Results have been extremely encouraging.
Motivated from the idea of "graphical structure plus number theory", two new set-colorings subject to some constraint sets are defined: one is the strong set-coloring (F, F') with the edge ...set-labelling F' induced by the vertex set-labelling F, and other one is the strongly total set-coloring. We show that every simple, connected (p,q)-graph G admits a strongly total set-labelling, and any tree having a super edge-magic total labelling admits a 2-uniform strongly total set-coloring.
We address the problem of code generation for DSP systems on a chip. In such systems, the amount of silicon devoted of program ROM is limited, so application software must be sufficiently dense. ...Additionally, the software must be written so as to meet various high-performance constraints, which may include hard real-time constraints. Unfortunately, current compiler technology is unable to generate high-quality code for DSPs, whose architectures are highly irregular. Thus, designers often resort to programming application software in assembly—a time-consuming task.
In this paper, we focus on providing support for architectural feature of DSPs that makes code generation difficult, namely multiple data memory banks. This feature increases memory bandwith by permitting multiple data memory accesses to occur in parallel when the referenced variables belong to different data memory banks and the registers involved conform to a strict set of conditions. We present an algorithm that attempst to maximize the benefit of this architectural feature. While previous approaches have decoupled the phases of register allocation and memory bank assignment, thereby compromising code quality, our algorithm performs these two phases simultaneously. Experimental results demonstrate that our algorithm not only generates high-quality compiled code, but also improves the quality of completely-referenced code.
PDF
