Search Results - clique
-
21
On the on-line coloring of unit interval graphs with proper interval representation
Published 2025-02-01“…For every positive integer $\omega$, we define the value $R(\omega)$ as the maximum number of colors for which Builder has a strategy that forces Algorithm to use $R(\omega)$ colors with the restriction that the unit interval graph constructed cannot contain a clique of size $\omega+1$. In 1981, Chrobak and \'{S}lusarek showed that $R(\omega)\leq2\omega -1$. …”We define the problem as a two-player game between Algorithm and Builder. The game is played in rounds. Each round, Builder presents an interval that is neither contained in nor contains any previously presented interval. Algorithm immediately and irrevocably assigns the interval a color that has no...
Get full text
Article -
22
On OCT Image Classification via Deep Learning
Published 2019-01-01“…Several network models with effective feature of reusable feature were compared and the transfer learning on networks with pre-trained models was realized. CliqueNet achieves better, classification results compared with other network models with a more than 0.98 accuracy and 0.99 of area under the curve (AUC) value finally.…”Computer-aided diagnosis of retinopathy is a research hotspot in the field of medical image classification. Diabetic macular edema (DME) and age-related macular degeneration (AMD) are two common ocular diseases that can result in partial or complete loss of vision. Optical coherence tomography imagi...
Get full text
Article -
23
Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs
Published 2021-06-01“…The article investigates NP-complete problems on pre-fractal graphs: a Hamiltonian cycle, a skeleton with the maximum number of pendant vertices, a monochromatic triangle, a clique, an independent set. The conditions under which for some problems it is possible to obtain an answer about the existence and to construct polynomial (when fixing the number of seed vertices) algorithms for finding solutions are identified.…”Modern network systems (unmanned aerial vehicles groups, social networks, network production chains, transport and logistics networks, communication networks, cryptocurrency networks) are distinguished by their multi-element nature and the dynamics of connections between its elements. A number of di...
Get full text
Article -
24
Temporal Ramsey Graphs: The Ramsey Kinematic Approach to the Motion of Systems of Material Points
Published 2025-04-01“…An infinite monochromatic (violet or orange) clique will necessarily appear in the graph. Applications of the introduced approach are discussed. …”The Ramsey approach is applied to analyses of the kinematics of systems built of non-relativistic, motile point masses/particles. This approach is based on colored graph theory. Point masses/particles serve as the vertices of the graph. The time dependence of the distance between the particles deter...
Get full text
Article -
25
Quantum compilation toolkit for Rydberg atom arrays with implications for problem hardness and quantum speedups
Published 2025-08-01“…The first module (reducer) provides hardware-agnostic and deterministic reduction logic that iteratively reduces the problem size via lazy clique removals. We find that real-world networks can typically be reduced by orders of magnitude on subsecond timescales, thus significantly cutting down the eventual load for quantum devices. …”We propose and implement a comprehensive quantum compilation toolkit for solving the maximum independent set (MIS) problem on quantum hardware based on Rydberg atom arrays. Our end-to-end pipeline involves three core components to efficiently map generic MIS instances onto Rydberg arrays with unit-d...
Get full text
Article -
26
Divisor equitably strong non-split divisor equitable domination in graphs
Published 2025-02-01“…In this paper, we introduce the concept of a non-split divisor equitable dominating set, divisor equitably strong non-split divisor equitable dominating set, and divisor equitable independent set and divisor equitable clique number. It also explores the concepts of a divisor equitable vertex dominating set, complement divisor equitable graph, and divisor equitable vertex cut. …”In epidemiology, the spread of diseases can be modelled using graphs, where individuals are nodes, and edges represent potential pathways for disease transmission. A non-split dominating set could help identify key individuals (or groups) whose monitoring or immunization would ensure that the rest...
Get full text
Article -
27
REDUCING GRAPHS BY LIFTING ROTATIONS OF EDGES TO SPLITTABLE GRAPHS
Published 2024-12-01“…A graph \(G\) is splittable if its set of vertices can be represented as the union of a clique and a coclique. We will call a graph \(H\) a splittable ancestor of a graph \(G\) if the graph \(G\) is reducible to the graph \(H\) using some sequential lifting rotations of edges and \(H\) is a splittable graph. …”A graph \(G\) is splittable if its set of vertices can be represented as the union of a clique and a coclique. We will call a graph \(H\) a splittable ancestor of a graph \(G\) if the graph \(G\) is reducible to the graph \(H\) using some sequential lifting rotations of edges and \(H\) is a splittab...
Get full text
Article -
28
Optimized fiducial marker placement using B‐spline surface modeling and graph theory for Cyberknife stereotactic body radiotherapy for superficial tumors
Published 2025-06-01“…To enhance the computational efficiency, a kd‐tree spatial indexing structure was integrated with graph theory, specifically the Bron–Kerbosch algorithm for maximal clique detection. The proposed method achieved a time complexity of O(mlogm+m2+3n3), demonstrating a significant improvement over the brute‐force O(n3) approach. …”Abstract CyberKnife, an established noninvasive stereotactic radiotherapy technology, has been extensively utilized to treat various malignancies because of its high precision and conformal dose delivery. The success of CyberKnife treatment is crucially dependent on optimal fiducial marker placement...
Get full text
Article -
29
Characterizing Duodenal Immune Microenvironment in Functional Dyspepsia: An AutoML-Driven Diagnostic Framework
Published 2025-07-01“…The top 20 critical genes were selected using maximal clique centrality (MCC), and a diagnostic model was developed using LASSO regression and multivariate logistic regression. …”Xueping Zhang,1,* Xingfu Fan,2,* Xinxin Hu,1 Zixing Qian,3 Jiaxuan Li,3 Wenyu Wu,1 Lei Chen,1 Suowei Wu,4 Lixin Ma,4 Chen Yang,5 Tao Zhang,1 Xiaolan Su,1 Wei Wei1 1Department of Gastroenterology, Beijing Key Laboratory of Functional Gastrointestinal Disorders Diagnosis and Tr...
Get full text
Article -
30
A very sharp threshold for first order logic distinguishability of random graphs
Published 2025-07-01“…(The formula of course states that $G$ contains a clique of size $k$.) The paper proves a much more precise result than this, obtaining the right bound for $k$ up to an additive constant. …”A very sharp threshold for first order logic distinguishability of random graphs, Discrete Analysis 2025:6, 17 pp. Let $G_1$ and $G_2$ be two independent random graphs with $n$ vertices. The probability that they are isomorphic is very small, but they nevertheless share many important properties: t...
Get full text
Article -
31
About Berge–Füredi’s conjecture on the chromatic index of hypergraphs
Published 2025-04-01“…This provides sharp information in connection with the Erdős–Faber–Lovász conjecture which deals with the coloring of a family of cliques that intersect pairwise in at most one vertex.…”We prove that the chromatic index of a hypergraph $\mathcal{H}$ satisfies the Berge–Füredi conjectured bound $\mathrm{q}(\mathcal{H}\le \Delta \bigl ([\mathcal{H}_2]\bigr )+1$ under certain hypotheses on the antirank $\mathrm{ar}(\mathcal{H})$ or on the maximum degree $\Delta (\mathcal{H})$. This pr...
Get full text
Article -
32
Vector Field Heterogeneity for the Assessment of Locally Disorganised Cardiac Electrical Propagation Wavefronts From High-Density Multielectrodes
Published 2024-01-01“…To quantify it, a novel heterogeneity parameter based on vector field analysis is proposed, utilising finite differences to measure direction changes between adjacent cliques. The proposed Vector Field Heterogeneity metric has been evaluated on a set of simulations with controlled levels of organisation in vector maps, and a variety of grid sizes. …”High-density multielectrode catheters are becoming increasingly popular in cardiac electrophysiology for advanced characterisation of the cardiac tissue, due to their potential to identify impaired sites. These are often characterised by abnormal electrical conduction, which may cause locally disorg...
Get full text
Article