The human brain cortex is very complex structure containing folds (gyri) and fissures (sulci) that were the subject of our study in this paper. The sulcus is one of the most important features in ...order to know the different functions areas of the brain. The exact identification of sulci on human brain using MRI images is helpful in many studies and applications related to brain diseases and human behavior. Automatic labeling of cortical sulci with all this complexity and inter-subject variability, this is considered non-trivial task. In this paper, we have proposed a new graph based approach of automatic labeling of cortical sulci with parallel and distributed algorithms using graph matching and generalized median graph. The graph matching is very important in many studies and applications such as pattern recognition and classification. The generalized median graph of a set of graphs is a way to represent a set of graphs by a comprehensive graph that minimizes the sum of the distances to all graphs. We have used the characteristics of shape, orientation and location to describe the sulci. The results that we have obtained prove that our approach is accurate and acceptable in this field which uses the graph matching for automatic labeling of cortical sulci.
Quasi-median graphs are a tool commonly used by evolutionary biologists to visualise the evolution of molecular sequences. As with any graph, a quasi-median graph can contain cut vertices, that is, ...vertices whose removal disconnect the graph. These vertices induce a decomposition of the graph into blocks, that is, maximal subgraphs which do not contain any cut vertices. Here we show that the special structure of quasi-median graphs can be used to compute their blocks without having to compute the whole graph. In particular we present an algorithm that, for a collection of n aligned sequences of length m, can compute the blocks of the associated quasi-median graph together with the information required to correctly connect these blocks together in run time O(n2m2), independent of the size of the sequence alphabet. Our primary motivation for presenting this algorithm is the fact that the quasi-median graph associated to a sequence alignment must contain all most parsimonious trees for the alignment, and therefore precomputing the blocks of the graph has the potential to help speed up any method for computing such trees.
A location function on a finite connected graph G takes as input any k-tuple of vertices (a profile) and outputs a single vertex. If G is a full y gated graph, then a target location function is ...defined by a predetermined vertex (the target) and outputs the unique vertex belonging to the convex closure of the profile which is closest to the target. If G is a finite tree, then any target function on G satisfies two conditions known in the literature as Pareto efficiency and replacement domination. We give a simple example to show that these two conditions do not characterize target functions on trees. A new condition, called the neighborhood condition, is introduced and we prove that target functions on trees are the only location functions satisfying Pareto efficiency, replacement domination, and the neighborhood condition.
Let G be a plane elementary bipartite graph with more than two vertices. Then its resonance graph Z(G) is a median graph and the set M(G) of all perfect matchings of G with a specific partial order ...is a finite distributive lattice. In this paper, we prove that Z(G) is cube-free if and only if it can be obtained from an edge by a sequence of convex path expansions with respect to a reducible face decomposition of G. As a corollary, a structure characterization is provided for G whose Z(G) is cube-free. Furthermore, Z(G) is cube-free if and only if the Clar number of G is at most two, and sharp lower bounds on the number of perfect matchings of G can be expressed by the number of finite faces of G and the number of Clar formulas of G. It is known that a cube-free median graph is not necessarily planar. Using the lattice structure on M(G), we show that Z(G) is cube-free if and only if Z(G) is planar if and only if M(G) is an irreducible sublattice of m×n. We raise a question on how to characterize irreducible sublattices of m×n that are M(G).
We introduce the operation of composition of domains and show that it reduces the classification of symmetric maximal Condorcet domains to the indecomposable ones. The only non-trivial indecomposable ...symmetric maximal domains known are the domains consisting of four linear orders examples of which were given by Raynaud (
1981
) and Danilov and Koshevoy (Order
30
(1), 181–194
2013
). We call them Raynaud domains and we classify them in terms of simple permutations, a well-researched combinatorial object. We hypothesise that no other indecomposable symmetric maximal domains exist.
The Edge General Position Problem Manuel, Paul; Prabha, R.; Klavžar, Sandi
Bulletin of the Malaysian Mathematical Sciences Society,
11/2022, Letnik:
45, Številka:
6
Journal Article
Recenzirano
Odprti dostop
Given a graph
G
, the general position problem is to find a largest set
S
of vertices of
G
such that no three vertices of
S
lie on a common geodesic. Such a set is called a
gp
-
set
of
G
, and its ...cardinality is the
gp
-
number
,
gp
(
G
)
, of
G
. In this paper, the edge general position problem is introduced as the edge analogue of the general position problem.The edge general position number,
gp
e
(
G
)
, is the size of a largest edge general position set of
G
. For
r
-dimensional hypercube
Q
r
, it is proved that
gp
e
(
Q
r
)
=
2
r
, and for arbitrary tree
T
, it is shown that
gp
e
(
T
)
is the number of its leaves. The value of
gp
e
(
P
r
□
P
s
)
is determined for every
r
,
s
≥
2
. To derive these results, the theory of partial cubes is used. Mulder’s meta-conjecture on median graphs is also discussed along the way.
In a cooperative game, coalitions are the fundamental behavioral units. Stable outcomes (in the core) are those blocked by no coalition. This paper has two objectives. First, building on the notion ...of intermediate preferences indexed by a median graph, I unify and extend previous results on the existence of stable outcomes in simple games. Second, I review how and when the core approach applies in more general settings and may help to predict the stable splitting of a whole group into disjoint coalitions.
Let G be a 2-connected outerplane bipartite graph and R(G) be its resonance graph. It is known that R(G) is a median graph. Assume that s is a reducible face of G and H is the subgraph of G obtained ...by removing all internal vertices (if exist) and edges on the common periphery of s and G. We show that R(G) can be obtained from R(H) by a peripheral convex expansion. As an application, we prove that Θ(R(G)) is a tree and isomorphic to the inner dual of G, where Θ(R(G)) is the induced graph on the Djoković–Winkler relation Θ-classes of R(G).
In real life, the types of anomalous events are diverse and low-frequency, and the collection and labeling of training data is complex. However, most detection algorithms are based on training data ...and test data, which are difficult to adapt to various monitoring scenarios. In this paper, we propose a video
A
nomaly
D
etection algorithm based on
G
raph
S
tructure
C
hange detection, which we call ADGSC. Firstly, we use key frame technique to pre-process the video and enhance the pseudo-periodicity of the video data. Second, our approach proposes an improved DTW algorithm for pseudo-periodicity estimation, which transforms periodicity estimation into a global matching growth rate optimization problem. Thus, the periodicity calculation no longer requires a priori knowledge or parameter settings and can be automatically computed in practical applications. Then, we stitch the normalized HSV histogram and HOG feature descriptors into feature vectors following the period obtained in the previous step for feature extraction of key frames. Further, a sliding window is used to build a graph model to measure the temporal variation of the video data, and median plot denoising is used to reduce the errors caused by feature extraction and metric methods, reduce background, blur and other noise interference, and improve the detection effect. Finally, we use box-line plots and box-line graphs to make decisions. Since we do not use deep learning methods, the evaluation metrics AUC and ROC applied for deep learning are no longer applicable to this method. Instead, our experiments use precision, recall, and F-value, which are commonly used in anomaly detection, to measure the effectiveness of our method. Experiment results show that our algorithm outperforms other current algorithms with unsupervised, adaptive, fault-tolerant, and real-time performance.
PDF
