Article
Engineering, Electrical & Electronic
M. Sh. Levin
Summary: This paper solves the problem of clique partitioning of a graph and investigates three basic types of this problem: maximum edge clique partitioning, minimum edge clique partitioning, and clique partitioning with bounded cardinality. It also proposes new multicriteria problem formulations based on vector weights and briefly reviews methods for clique designing and solving clique partitioning problems in graphs. Furthermore, it discusses the problem of constructing a clique trajectory over a dynamic graph and provides numerical examples to illustrate the investigated problems.
JOURNAL OF COMMUNICATIONS TECHNOLOGY AND ELECTRONICS
(2022)
Article
Computer Science, Interdisciplinary Applications
Xiangjing Lai, Jin-Kao Hao, Zhang-Hua Fu, Dong Yue
Summary: The capacitated clustering problem is a general model relevant for a variety of important applications. This work presents an original and highly effective algorithm for solving this problem, which significantly outperforms existing state-of-the-art algorithms in the literature. The key feature of the algorithm, combining neighborhood decomposition-driven local search with perturbation, can be useful for designing effective heuristic algorithms for other important clustering problems.
COMPUTERS & OPERATIONS RESEARCH
(2021)
Article
Computer Science, Artificial Intelligence
Joel Mackenzie, Matthias Petri, Alistair Moffat
Summary: Connectivity graphs and linked data are crucial for the information access systems in social media and web search services. The Bipartite Graph Partitioning (BP) mechanism enhances compressibility and reduces storage space occupied by large sparse graphs. We have developed algorithmic and heuristic refinements to BP, resulting in faster computation of space-reducing vertex orderings. Our implementation executes up to four times faster than the baseline implementation, while maintaining compressibility.
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
(2023)
Article
Computer Science, Information Systems
Yuki Hidaka
Summary: This paper presents a novel multi-material topology optimization method for electric motors, which combines combinatorial optimization and multi-material topology optimization to obtain high-performance design solutions for complex motors.
Article
Computer Science, Artificial Intelligence
Shengwei Ji, Chenyang Bu, Lei Li, Xindong Wu
Summary: Graph edge partitioning is essential for distributed graph computation systems, and existing models can be classified as offline or streaming. This study introduces a Local Graph Edge Partitioning model that considers only local information to improve efficiency. Two local graph edge partitioning algorithms based on this model outperform rivals in most tested cases and significantly improve the efficiency of the real graph computation system GraphX.
ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY
(2021)
Article
Computer Science, Artificial Intelligence
Yuji Zou, Jin-Kao Hao, Qinghua Wu
Summary: This article presents an effective heuristic algorithm for the traveling salesman problem with job-times. The algorithm uses a breakout local search method to find high-quality local optimal solutions and incorporates a perturbation procedure to escape local optimum traps. Computational results show that the algorithm outperforms previous methods on benchmark instances.
EXPERT SYSTEMS WITH APPLICATIONS
(2023)
Article
Computer Science, Information Systems
Jian Gao, Xiaoxia Tao, Shaowei Cai
Summary: We propose a local search algorithm called FastCCP to solve the constrained clustering problem by integrating user constraints. The algorithm merges instances connected by must-link constraints into nodes and performs a local search method to handle cannot-link constraints while minimizing WCSS. Several strategies are proposed to enhance solution diversity and achieve a trade-off between constraint satisfaction and WCSS minimization. Experimental results show that our algorithm outperforms state-of-the-art algorithms in terms of solution quality and CPU runtime.
INFORMATION SCIENCES
(2023)
Article
Biochemical Research Methods
Ulavappa B. Angadi, Krishna Kumar Chaturvedi, Sudhir Srivastava, Anil Rai
Summary: A novel methodology has been developed for comparing protein 3D structures by converting them into 2D graphs, partitioning them into sub-graphs, and matching them to calculate similarity, showing efficient time complexity, accuracy, and relevant grouping of proteins in structural groups.
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
(2021)
Article
Mathematics
Jose Garcia, Jose Lemus-Romani, Francisco Altimiras, Broderick Crawford, Ricardo Soto, Marcelo Becerra-Rozas, Paola Moraga, Alex Paz Becerra, Alvaro Pena Fritz, Jose-Miguel Rubio, Gino Astorga
Summary: This article proposes a hybrid algorithm that integrates the k-means algorithm into a binary version of cuckoo search to solve the NP-hard Set-Union Knapsack Problem. Numerical experiments show that the hybrid algorithm consistently produces superior results in most medium instances, but its performance degrades in large instances.
Article
Computer Science, Artificial Intelligence
Zhongbo Hu, Ting Zhou, Qinghua Su, Mianfang Liu
Summary: This paper proposes a niching backtracking search algorithm with adaptive local search to address the problem of multimodal multiobjective optimization. By adopting the affinity propagation clustering method to form multiple niches and developing a novel mutation based on affinity propagation clustering, the algorithm shows improved performance. Experimental results demonstrate that the proposed algorithm outperforms other algorithms in various benchmark functions and practical application problems.
SWARM AND EVOLUTIONARY COMPUTATION
(2022)
Article
Automation & Control Systems
Pengfei He, Jin-Kao Hao
Summary: The Colored Traveling Salesmen Problem (CTSP) is a generalization of the popular Traveling Salesman Problem, involving multiple salesmen; The goal is to determine the shortest Hamiltonian circuit for each salesman, satisfying specific conditions; It is known to be computationally challenging, and a solution has been proposed.
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
(2021)
Article
Computer Science, Artificial Intelligence
Shabnam Nazmi, Xuyang Yan, Abdollah Homaifar, Mohd Anwar
Summary: This paper proposes a rule-based evolutionary multi-label classification method that incorporates local label correlations through graph structures, estimated label similarities, and hierarchical density-based clustering. The method aims to improve classification accuracy by modeling label dependencies and refining high-order label relations. Experimental results on benchmark datasets show that the proposed method outperforms several well-known multi-label classification algorithms with statistical significance.
KNOWLEDGE-BASED SYSTEMS
(2021)
Article
Computer Science, Interdisciplinary Applications
Duy Hoang Tran, Behrouz Babaki, Dries Van Daele, Pieter Leyman, Patrick De Causmaecker
Summary: This paper presents an iterated local search algorithm for constrained graph clustering in biological networks, aiming to find the clustering with the highest quality in a short computing time. Experiments demonstrate the proposed algorithm's good quality and efficiency, outperforming existing branch-and-cut algorithms and producing competitive results with other local search techniques and graph clustering algorithms. Additionally, a multilevel algorithm for clustering is designed to handle large-scale graphs, achieving promising results on various coarsening methods applied to biological networks exceeding 10,000 genes.
COMPUTERS & OPERATIONS RESEARCH
(2021)
Article
Computer Science, Information Systems
Rafael A. Melo, Celso C. Ribeiro, Jose A. Riveaux
Summary: This paper formally introduces the minimum quasi-clique partitioning problem and proposes four integer programming formulations and a heuristic algorithm to solve the problem. Computational experiments show that the formulations employing the principles of representatives outperform others. The results also indicate that instances with medium values of y are more challenging.
INFORMATION SCIENCES
(2022)
Article
Management
Luis Evaristo Caraballo, Jose-Miguel Diaz-Banez, Nadine Kroher
Summary: Clustering aims to discover natural groups in datasets without assuming any prior knowledge, by detecting inherent separations using a similarity function and formulating the task as a graph partitioning problem. Our algorithm introduces a new cluster quality measure based on variance ratios to compute optimal clustering in polynomial time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2021)
Article
Transportation
J. A. Pavlik, I. G. Ludden, S. H. Jacobson
Summary: The transmission of SARS-CoV-2 on airplanes is a significant concern, and reducing transmission risks can save lives. This study analyzes various risk models and introduces two new ones based on experiments conducted on real aircraft. Recommendations on optimal seating arrangements are provided for each risk model.
JOURNAL OF AIR TRANSPORT MANAGEMENT
(2022)
Article
Health Policy & Services
Ian G. Ludden, Sheldon H. Jacobson, Janet A. Jokela
Summary: The study compares mortality data for different age and sex subgroups in 2021 with previous years, both with and without COVID-19 deaths. It finds that mortality risks in 2021 were significantly higher than in the years before, regardless of COVID-19 involvement. The mortality risks for the 25-54 age group were higher in 2021 compared to 2020, while the total mortality risks for the 65+ age groups declined. The next few years may see mortality risks falling below pre-pandemic levels, especially for those excluding COVID-19 deaths.
HEALTH CARE MANAGEMENT SCIENCE
(2022)
Article
Management
Kiera W. Dobbs, Rahul Swamy, Douglas M. King, Ian G. Ludden, Sheldon H. Jacobson
Summary: Every 10 years, U.S. states redraw their congressional and state legislative district plans, which determines the political landscape for the next 10 years. Missouri enacted new criteria for state legislative districts before the 2021 redistricting cycle. The authors were contacted by the Missouri League of Women Voters (LWV-MO) to analyze the potential impact of these new criteria on the map-drawing process and found that Missouri's political geography and constitutional requirements hinder the improvement of political fairness in state legislative plans but can substantially improve fairness in Missouri congressional plans.
INFORMS JOURNAL ON APPLIED ANALYTICS
(2023)
Article
Business
John A. Pavlik, Ian G. Ludden, Sheldon H. Jacobson, Edward C. Sewell
Summary: The article discusses the transmission risks of SARS-CoV-2 on airplanes and introduces the airplane seating assignment problem (ASAP) to reduce transmission risk. Research shows that seating assignments provided by the proposed models have lower aggregate risk than the strategy of blocking the middle seats for the same number of passengers. Future efforts should focus on developing risk models based on SARS-CoV-2 to better address the pandemic.
Article
Social Sciences, Mathematical Methods
Ian G. Ludden, Arash Khatibi, Douglas M. King, Sheldon H. Jacobson
JOURNAL OF QUANTITATIVE ANALYSIS IN SPORTS
(2020)
Article
Mathematics, Applied
Yuehua Bu, Peng Wang, Hongguo Zhu, Junlei Zhu
Summary: This paper investigates the injective-edge coloring of a sparse graph G, and proves that when mad(G) meets certain conditions, the injective chromatic index x(i)'(G) has a upper bound.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Fawad Ali, Bilal A. Rather, Muhammad Naeem, Wei Wang
Summary: A topological descriptor is a numerical value derived from the molecular structure and is related to the important structural characteristics of the molecule. It is used to describe the composition of chemicals and their relationship with physical properties. This article explores various topological indices for power graphs of different finite groups.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Sergio Bermudo, Roslan Hasni, Fateme Movahedi, Juan E. Napoles
Summary: This article introduces a new graph index, the geometric-arithmetic index, and discusses the upper and lower bounds for this index in trees.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Ran Gu, Hui Lei, Yongtang Shi, Yiqiao Wang
Summary: This paper discusses the existence of rainbow-free coloring in random k-uniform hypergraphs, and provides the threshold function and the answer.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Fengwei Li, Qingfang Ye, Huajing Lu
Summary: This paper introduces the definition and application of the atom-bond sum-connectivity index (ABS index), and discusses its importance in studying molecular structures.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Milan Basic
Summary: This passage mainly describes the definition of integral circulant graph ICGn(D), the condition for adjacent vertices, and the characterization of minimal spread in the class of connected integral circulant graphs of a given order.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Andrey A. Dobrynin, Konstantin V. Vorob'ev
Summary: This study investigates the relationship between the Wiener index and R-m(G) of a graph G, and establishes the existence and properties of graphs G that satisfy specific conditions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Devsi Bantva, Daphne Der-Fen Liu
Summary: This paper provides a lower bound for the radio number of the Cartesian product of two trees and presents three necessary and sufficient conditions as well as three sufficient conditions for achieving this bound. By applying these results, the radio number of the Cartesian product of two stars as well as a path and a star is determined.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Mikhail Fadin
Summary: This article discusses rational lattices, octahedral defects, and their relationship with monotonic increasing functions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Jian Lu, Huiqing Liu, Xiaolan Hu
Summary: This paper investigates the problem of strong edge-coloring, and proves that when certain conditions are satisfied, the upper bound of the strong chromatic index is 29, thereby verifying Erdos' conjecture under certain circumstances.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Tom Denat, Ararat Harutyunyan, Nikolaos Melissinos, Vangelis Th. Paschos
Summary: This paper studies the average-case complexity of a branch-and-bound algorithm for the MIN DOMINATING SET problem in random graphs. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Lkhagva Buyantogtokh, Batmend Horoldagva
Summary: This paper discusses the application of the exponential second Zagreb index in graphs and proves a conjecture regarding the maximum index. It also identifies the properties of graphs with maximum index under certain conditions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Shenwei Huang, Yiao Ju, T. Karthick
Summary: This paper studies the coloring of (P5, kite)-free graphs with small clique number. It provides color number bounds for different constraints on cliques and proves them for specific conditions. The paper also gives examples to demonstrate the tightness of the bounds and makes a conjecture for the more general case.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Ryul Kim
Summary: This paper establishes relations between irreducible polynomials over a finite field Fq and its quadratic extension Fq2. The paper considers the relation between the numbers of irreducible polynomials of a fixed degree over Fq and Fq2, as well as the relations between self-reciprocal irreducible polynomials over Fq and self-conjugatereciprocal irreducible polynomials over Fq2. The paper also provides formulas for the number and the product of all self-conjugate-reciprocal irreducible monic (SCRIM) polynomials over Fq2.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Beata Benyi, Sithembele Nkonkobe
Summary: This paper introduces and lists weighted alpha-distanced words, showing their connection to the unified Apostol-type polynomials and providing combinatorial proofs of certain identities.
DISCRETE APPLIED MATHEMATICS
(2024)
