Given an on-going sports competition, with each team having a current score and some matches left to be played, we ask whether it is possible for our distinguished team
t
to obtain a final standing ...with at most
r
teams finishing before
t
. We study the computational complexity of this problem, addressing it both from the viewpoint of parameterized complexity and of approximation. We focus on a special case equivalent to finding a maximal induced subgraph of a given graph
G
that admits an orientation where the in-degree of each vertex is upper-bounded by a given function. We obtain a
Θ
(
log
|
V
(
G
)
|
)
approximation for this problem based on an asymptotically optimal approximation we present for a certain matroid problem in which we need to cover a base of a matroid by picking elements from a set family.
We investigate the following modification of the well-known
irregularity strength of graphs. Given a total weighting
w
of a graph
G
=
(
V
,
E
)
with elements of a set
{
1
,
2
,
…
,
s
}
, denote
w
t
G
...(
v
)
=
∑
e
∋
v
w
(
e
)
+
w
(
v
)
for each
v
∈
V
. The smallest
s
for which exists such a weighting with
w
t
G
(
u
)
≠
w
t
G
(
v
)
whenever
u
and
v
are distinct vertices of
G
is called the
total vertex irregularity strength of this graph, and is denoted by
tvs
(
G
)
. We prove that
tvs
(
G
)
≤
3
⌈
n
/
δ
⌉
+
1
for each graph of order
n
and with minimum degree
δ
>
0
.
A labelling of the n-dimensional hypercube Hn is a mapping that assigns value 0 or 1 to each edge of Hn. A labelling is antipodal if antipodal edges of Hn get assigned different values. It has been ...conjectured that, if Hn,n≥2, is given a labelling that is antipodal, then there exists a pair of antipodal vertices joined by a monochromatic path. This conjecture has been verified by hand for n≤5. In this paper, we verify the conjecture in the case where the labelling is simple in the sense that no square xyzt in Hn has value 0 assigned to xy,zt and value 1 assigned to yz,tx, even if the given labelling is not antipodal. The proof is based on a new property of (not necessarily antipodal) simple labellings of Hn. We also exhibit a large class of simple labellings that thus satisfy the conjecture. Finally, we conjecture that, even if the given labelling is not antipodal, there is always a path joining antipodal vertices that switches labels at most once, which implies the original conjecture. We establish this new conjecture for Hn,n≤5 as well.
In this work, a systematic review of heuristics for profile reduction of symmetric matrices is presented. 74 heuristics tested for reduction profile were found. Researchers compared results of their ...heuristics with results of other heuristics. In this review, these comparisons were analyzed and 8 heuristics were identified as the possible best for the problem. In addition, exchange methods, a form of local search, were identified that can benefit heuristics identified as the best ones for the task.
A modular multiplicative divisor (MMD) labelling of a graph G with p vertices and q edges is a bijection f from the set of all vertices to the set of positive integers {1, 2,…,p} such that the sum of ...all edge labels f*(uv)=f(u)f(v)(modp); uv∈E(G) is a multiple of p. In this paper, we characterize certain classes of MMD graphs. This result is a solution to the open problem posed by G. Sethuraman in AKCE International Journal of Graphs and Combinatorics, No. 1 (2009) 229–236. In addition, we discuss the role of MMD labelling in obtaining cyclic decompositions of certain families of graphs into specific graphs.
We investigate the
group irregularity strength
(
s
g
(
G
)
) of graphs, that is, we find the minimum value of
s
such that for any Abelian group
G
of order
s
, there exists a function
f
:
E
(
G
)
→
G
...such that the sums of edge labels at every vertex are distinct. We prove that for any connected graph
G
of order at least
3
,
s
g
(
G
)
=
n
if
n
≠
4
k
+
2
and
s
g
(
G
)
≤
n
+
1
otherwise, except the case of an infinite family of stars. We also prove that the presented labelling algorithm is linear with respect to the order of the graph.
Getting a labelling of vertices close to the structure of the graph has been proved to be of interest in many applications, e.g. to follow signals indexed by the vertices of the network. This ...question can be related to a graph labelling problem known as the cyclic bandwidth sum problem (CBSP). It consists of finding a labelling of the vertices of an undirected and unweighted graph with distinct integers such that the sum of (cyclic) difference of labels of adjacent vertices is minimized. In this paper, we introduce a new heuristic to follow the structure of the graph, by finding an approximate solution for the CBSP. Although theoretical results exist that give optimal value of cyclic bandwidth sum (CBS) for standard graphs, there are neither results for real-world complex networks, nor explicit methods to reach this optimal result. Furthermore, only a few methods have been proposed to approximately solve this problem. The heuristic we propose is a two-step algorithm: the first step consists of traversing the graph to find a set of paths which follow the structure of the graph, using a similarity criterion based on the Jaccard index to jump from one vertex to the next one. The second step is the merging of all obtained paths, based on a greedy approach that extends a partial solution by inserting a new path at the position that minimizes the CBS. The effectiveness of the proposed heuristic is shown through experiments on graphs whose optimal value of CBS is known, as well as on complex networks, where the consistency between labelling and topology is highlighted.
Graph labelling is a key activity of network science, with broad practical applications, and close relations to other network science tasks, such as community detection and clustering. While a large ...body of work exists on both unsupervised and supervised labelling algorithms, the class of random walk-based supervised algorithms requires further exploration, particularly given their relevance to social and political networks. This work refines and expands upon a new semi-supervised graph labelling method, the GLaSS method, that exactly calculates absorption probabilities for random walks on connected graphs. The method models graphs exactly as discrete-time Markov chains, treating labelled nodes as absorbing states. The method is applied to roll call voting data for 42 meetings of the United States House of Representatives and Senate, from 1935 to 2019. Analysis of the 84 resultant political networks demonstrates strong and consistent performance of GLaSS when estimating labels for unlabelled nodes in graphs, and reveals a significant trend of increasing partisanship within the United States Congress.
Large sparse symmetric matrix problems arise in a number of scientific and engineering fields such as fluid mechanics, structural engineering, finite element analysis and network analysis. In all ...such problems, the performance of solvers depends critically on the sum of the row bandwidths of the matrix, a quantity known as
envelope size
. This can be reduced by appropriately reordering the rows and columns of the matrix, but for an
N
×
N
matrix, there are
N
!
such permutations, and it is difficult to predict how each permutation affects the envelope size without actually performing the reordering of rows and columns. These two facts compounded with the large values of
N
used in practical applications, make the problem of minimising the envelope size of a matrix an exceptionally hard one. Several methods have been developed to reduce the envelope size. These methods are mainly heuristic in nature and based on graph-theoretic concepts. While metaheuristic approaches are popular alternatives to classical optimisation techniques in a variety of domains, in the case of the envelope reduction problem, there has been a very limited exploration of such methods. In this paper, a Genetic Programming system capable of reducing the envelope size of sparse matrices is presented and evaluated against four of the best-known and broadly used envelope reduction algorithms. The results obtained on a wide-ranging set of standard benchmarks from the Harwell–Boeing sparse matrix collection show that the proposed method compares very favourably with these algorithms.
PDF
