Article
Computer Science, Software Engineering
Michael Anastos, Alan Frieze
Summary: In a seminal paper, Karp and Sipser proposed two algorithms for finding large matchings in sparse random graphs. Their empirical results suggest that the first algorithm is superior, and this paper proves that it is indeed more effective for random k-regular graphs. The algorithm can also be adapted to find a maximum matching in O(n) time w.h.p., a significant improvement over the worst-case O(n(3/2)) time complexity.
RANDOM STRUCTURES & ALGORITHMS
(2021)
Article
Computer Science, Hardware & Architecture
Che Jiang, Wanyue Xu, Xiaotian Zhou, Zhongzhi Zhang, Haibin Kan
Summary: In this paper, several combinatorial problems for two power-law graphs with the same characteristics are studied, and it is found that power-law behavior itself cannot fully characterize the combinatorial properties of heterogeneous graphs. This is important for the application of combinatorial problems in different fields.
Article
Computer Science, Software Engineering
Dehia Ait Ferhat, Zoltan Kiraly, Andras Sebo, Gautier Stauffer
Summary: This paper investigates the existence of k matchings that cover all nodes in a given undirected graph, known as a matching-k-cover problem. When k = 1, the problem is equivalent to finding a perfect matching. For k greater than 1, the paper provides a characterization condition and proves the existence using a simple polynomial algorithm. Surprisingly, the approach only uses bipartite matching techniques. The paper also introduces a new minimax theorem that leads to further results, generalizations, and connections between different problems.
MATHEMATICAL PROGRAMMING
(2022)
Article
Mathematics, Applied
Tomislav Doslic, Meysam Taheri-Dehkordi, Gholam Hossein Fath-Tabar
Summary: This article presents some results on perfect pseudomatchings with a small number of components in some classes of fullerene graphs.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Review
Computer Science, Information Systems
Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis
Summary: This paper investigates the maximum clique problem for graphs with small intersection number and random intersection graphs, presenting a simple algorithm to find a maximum clique in polynomial time, especially when the number of labels is not too large. The study also proves that inferring the complete information of label choices for each vertex from the resulting random intersection graph is solvable with a unique solution using the maximum likelihood estimation method. The research contributes to the field by introducing the Single Label Clique Theorem to address the problem of forming large cliques from more than one label.
COMPUTER SCIENCE REVIEW
(2021)
Article
Operations Research & Management Science
Joel Antonio Trejo-Sanchez, Francisco A. Madera-Ramirez, Jose Alberto Fernandez-Zepeda, Jose Luis Lopez-Martinez, Alejandro Flores-Lamas
Summary: This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. By decomposing the graph into smaller subgraphs and improving the solution by adding some vertices, the algorithm computes a near-optimal 2-packing set.
OPTIMIZATION LETTERS
(2023)
Article
Mathematics
Michael A. Henning, Anders Yeo
Summary: The paper discusses the complete description of the convex set Lk, lambda for all k greater than or equal to lambda, and also determines its extreme points.
JOURNAL OF GRAPH THEORY
(2022)
Article
Computer Science, Information Systems
Elad Aigner-Horev, Erel Segal-Halevi
Summary: An envy-free matching in a bipartite graph refers to a matching in which no unmatched vertex in X is adjacent to a matched vertex in Y. We prove the existence of a unique partition in every bipartite graph, where all envy-free matchings are contained within one of the partition sets. Based on this structural theorem, we present a polynomial-time algorithm for finding an envy-free matching with maximum cardinality.
INFORMATION SCIENCES
(2022)
Article
Multidisciplinary Sciences
Fahad Ur Rehman, Tabasam Rashid, Muhammad Tanveer Hussain
Summary: This paper introduces the concept and characteristics of bipolar fuzzy incidence graph, and explores its applications in selecting the best applicants and solving fuzzy maximization problems. By extending the concepts and theorems of fuzzy graphs, it provides more operations and theoretical foundation for BFIG.
Article
Mathematics, Applied
Yue Ma, Xinmin Hou, Jun Gao, Boyuan Liu, Zhi Yin
Summary: This article investigates rainbow independent sets in graphs and provides properties of the minimal number k under certain conditions. It also proves the validity of one conjecture assuming another conjecture is true.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Information Systems
Bohao Wu, Lingli Li
Summary: This paper introduces a framework called L2M, based on a deep reinforcement learning (DRL) model, for solving the maximum weighted matching (MWM) problem on large-scale general graphs. The framework represents MWM as a carefully designed Markov Decision Process (MDP) and incorporates pruning methods and an edge-message passing network to improve efficiency and effectiveness.
INFORMATION SCIENCES
(2022)
Article
Mechanics
Dor Minzer, Yaron Oz, Muli Safra, Lior Wainstain
Summary: Working within the multi-type Galton-Watson branching-process framework, we analyzed the spread of a pandemic through a general multi-type random contact graph. Our model, consisting of multiple communities, determines outbreak likelihood and calculates the size of the giant-connected-component of the graph to predict population infection rates. The pandemic spread is shown to have a natural evolution direction determined by the Perron-Frobenius eigenvector, with the basic reproduction number as the corresponding eigenvalue. Numerical simulations compare homogeneous and heterogeneous spread graphs, emphasizing the impact of countermeasures on infected population fractions.
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
(2021)
Article
Physics, Multidisciplinary
Ido Tishby, Ofer Biham, Eytan Katzav
Summary: This study presents analytical results for the distribution of cover times of random walks on random regular graphs, showing very good agreement with results obtained from computer simulations. The analysis includes deriving a master equation for the distribution of the number of distinct nodes visited by the random walk, calculating the cumulative distribution of cover times, and determining the distributions of partial cover and random cover times.
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
(2022)
Article
Computer Science, Software Engineering
Martin Balko, Manfred Scheucher, Pavel Valtr
Summary: This paper investigates the number of k-holes in a set of points randomly drawn from a convex body, and provides asymptotic lower bounds and exact values for certain cases. Additionally, it improves upon existing research in specific scenarios.
RANDOM STRUCTURES & ALGORITHMS
(2023)
Article
Statistics & Probability
Jian Ding, Hang Du
Summary: This paper focuses on recovering the latent vertex matching of two correlated graphs which are independently sub-sampled from a common Erdos-Renyi graph G(n, p) without labels. A sharp information-theoretic threshold is established to determine the possibility of correctly matching a positive fraction of vertices, when p = n-alpha +o(1) for alpha E (0, 1]. Our result improves a constant factor in a recent work by Wu, Xu and Yu.
ANNALS OF STATISTICS
(2023)