Parallelism Detection Using Graph Labelling Telegin, P. N.; Baranov, A. V.; Shabanov, B. M. ...
Lobachevskii journal of mathematics,
10/2022, Letnik:
43, Številka:
10
Journal Article
Recenzirano
Odprti dostop
Usage of multiprocessor and multicore computers implies parallel programming. Tools for preparing parallel programs include parallel languages and libraries as well as parallelizing compilers and ...convertors that can perform automatic parallelization. The basic approach for parallelism detection is analysis of data dependencies and properties of program components, including data use and predicates. In this article a suite of used data and predicates sets for program components is proposed and an algorithm for computing these sets is suggested. The algorithm is based on wave propagation on graphs with cycles and labelling. This method allows analysing complex program components, improving data localization and thus providing enhanced data parallelism detection.
The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This ...problem can be viewed as a graph labelling problem, where arcs receive labels that contribute to the score of both endpoints of the arc, and the aim is to label the arcs in a way that each vertex obtains a score not exceeding its capacity. We investigate the complexity of this problem in detail, using a multivariate approach to examine how various parameters of the input graph (such as the maximum degree, the feedback vertex/edge number, and different width parameters) influence the computational tractability. We obtain several efficient algorithms, as well as certain hardness results.
Total Weight Choosability of Graphs Przybyło, Jakub; Woźniak, Mariusz
The Electronic journal of combinatorics,
05/2011, Letnik:
18, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Suppose the edges and the vertices of a simple graph $G$ are assigned $k$-element lists of real weights. By choosing a representative of each list, we specify a vertex colouring, where for each ...vertex its colour is defined as the sum of the weights of its incident edges and the weight of the vertex itself. How long lists ensures a choice implying a proper vertex colouring for any graph? Is there any finite bound or maybe already lists of length two are sufficient? We prove that $2$-element lists are enough for trees, wheels, unicyclic and complete graphs, while the ones of length $3$ are sufficient for complete bipartite graphs. Our main tool is an algebraic theorem by Alon called Combinatorial Nullstellensatz.
Graph theory and its applications attract several researchers from different areas of research. It is used to model wide range of systems, for example in biological system and in studying chaotic ...systems. Decomposition of complex graphs into simple small graphs is very helpful to study that complex systems. A complete classification is given for circulant graphs of degree 5 that allow an Orthogonal Double Cover by some graphs. Whenever such a cover exists, an orthogonal labelling for the corresponding covering graph is presented. Our work here completes all previous incomplete work about this point.
Which Graphs Occur as γ-Graphs? DeVos, Matt; Dyck, Adam; Jedwab, Jonathan ...
Graphs and combinatorics,
07/2020, Letnik:
36, Številka:
4
Journal Article
Recenzirano
Odprti dostop
The
γ
-graph of a graph
G
is the graph whose vertices are labelled by the minimum dominating sets of
G
, in which two vertices are adjacent when their corresponding minimum dominating sets (each of ...size
γ
(
G
)
) intersect in a set of size
γ
(
G
)
-
1
. We extend the notion of a
γ
-graph from distance-1-domination to distance-
d
-domination, and ask which graphs
H
occur as
γ
-graphs for a given value of
d
≥
1
. We show that, for all
d
, the answer depends only on whether the vertices of
H
admit a labelling consistent with the adjacency condition for a conventional
γ
-graph. This result relies on an explicit construction for a graph having an arbitrary prescribed set of minimum distance-
d
-dominating sets. We then completely determine the graphs that admit such a labelling among the wheel graphs, the fan graphs, and the graphs on at most six vertices. We connect the question of whether a graph admits such a labelling with previous work on induced subgraphs of Johnson graphs.
Consider a simple graph G=(V,E) and its (proper) total colouring c with elements of the set {1,2,…,k}. We say that c is neighbour sum distinguishing if for every edge uv∈E, the sums of colours met by ...u and v differ, i.e., c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e). The least k guaranteeing the existence of such a colouring is denoted χ″∑(G). We investigate a daring conjecture presuming that χ″∑(G)≤Δ(G)+3 for every graph G, a seemingly demanding problem if confronted with up-to-date progress in research on the Total Colouring Conjecture itself.
We note that χ″∑(G)≤Δ(G)+2col(G)−1 and apply Combinatorial Nullstellensatz to prove a stronger bound: χ″∑(G)≤Δ(G)+⌈53col(G)⌉. This imply an upper bound of the form χ″∑(G)≤Δ(G)+const. for many classes of graphs with unbounded maximum degree. In particular we obtain χ″∑(G)≤Δ(G)+10 for planar graphs.
In fact we show that identical bounds also hold if we use any set of k real numbers instead of {1,2,…,k} as edge colours, and moreover the same is true in list versions of the both concepts.
We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2Ω(n2) n-vertex graphs as n→ ∞. This regime contains many classes of interest, for instance ...perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of n/4+o(n) bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of n/4+o(n) bits per vertex and comparability labelling scheme for posets with labels of n/4+o(n) bits per element. All these results are best possible, up to the lower order term.
We design cryptographical graphs for information security by the following principles: (1) be used conveniently in usually; (2) with strong security, that is, it is difficult to be broken; (3) there ...are enough graphs and labellings for making desired keys and locks. For answering the above problems, we prove the series cryptographical graphs have good properties, and show the guarantee for constructing large scale of cryptographical trees from smaller cryptographical trees. The methods used for constructing the desired cryptographical graphs can be transformed into efficient algorithms.
► One of the most important points on computing a graph prototype is to compute the common labelling among all graphs in the set. Most of the approaches up to date perform pair-wise graph matching ...operations in order to compute the common labelling. We present a set of methods to compute the common labelling considering all the knowledge of the set. ► The first two methods we present are based on computing a probability node assignation hyper-cube. This methods offer very good performance, however the high computational cost makes its use unfeasible with large graph sets. ► The third method we present is based on a new probabilistic framework. The method offers similar performance as the two initial methods but with a much lower computational cost. ► The results of the evaluation show that the methods we present offer best performance than up to date methods.
In some methodologies, it is needed a consistent common labelling between the vertices of a graph set, for instance, to compute a representative of a set of graphs. This is an NP-complete problem with an exponential computational cost depending on the number of nodes and the number of graphs. In the current paper, we present two new methodologies to compute a sub-optimal common labelling. The former focuses in extending the Graduated Assignment algorithm, although the methodology could be applied to other probabilistic graph-matching algorithms. The latter goes one step further and computes the common labelling whereby a new iterative sub-optimal algorithm. Results show that the new methodologies improve the state of the art obtaining more precise results than the most recent method with similar computational cost.
PDF
