Article
Management
Oylum Seker, Tinaz Ekim, Z. Caner Taskin
Summary: The paper investigates the selective graph coloring problem in perfect graphs using an exact cutting plane algorithm, and proposes a method to randomly generate perfect graphs. Computational experiments demonstrate that their solution strategy significantly improves the solvability of the problem.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2021)
Article
Mathematics, Applied
Huimin Bi, Xin Zhang
Summary: This article defines the d-defective incidence chromatic number of a graph, extends the notion of incidence chromatic number, and determines it for several classes of graphs including trees, complete bipartite graphs, complete graphs, and outerplanar graphs. The article also presents fast algorithms for constructing the optimal d-defective incidence colorings of these graphs.
APPLIED MATHEMATICS AND COMPUTATION
(2023)
Article
Computer Science, Artificial Intelligence
Yongjian Xu, Huabin Cheng, Ning Xu, Yu Chen, Chengwang Xie
Summary: A distribution evolutionary algorithm based on a population of probability model (DEA-PPM) is developed in this paper to efficiently solve the graph coloring problem. It utilizes a distribution population and a novel probability model, and introduces an orthogonal exploration strategy with the assistance of a refinement strategy. By sampling the distribution population, efficient search in the solution space is achieved based on a tabu search process.
SWARM AND EVOLUTIONARY COMPUTATION
(2023)
Article
Mathematics, Applied
Young-Soo Myung
Summary: The triangle packing problem aims to find the maximum number of pairwise vertex disjoint triangles in a given graph. It is known to be NP-complete in general and even so in chordal graphs. However, the problem can be solved in polynomial time for unit interval graphs. Hence, it remains an open question whether there exists a polynomial time algorithm to solve the triangle packing problem on interval graphs. This paper provides an answer to this problem.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Computer Science, Information Systems
Yun Peng, Xin Lin, Byron Choi, Bingsheng He
Summary: Graph coloring has broad applications in various fields, and our VColor and VColor* approaches address efficiency challenges in graph coloring. VColor* demonstrates superior efficiency compared to VColor in experimental evaluations.
FRONTIERS OF COMPUTER SCIENCE
(2021)
Article
Computer Science, Artificial Intelligence
Ping Guo, Bin Guo
Summary: This paper proposes a hybrid evolutionary algorithm NERS_HEAD for solving the graph coloring problem. The algorithm introduces a new elite replacement strategy to increase the diversity of the evolutionary population and enables the algorithm to jump out of local optimum states. Experimental results on 59 DIMACS benchmark instances demonstrate that NERS_HEAD can effectively improve the efficiency and success rate of solving graph coloring problems.
Article
Management
Rafael A. Melo, Michell F. Queiroz, Marcio C. Santos
Summary: The study introduces a new approach to solve the b-coloring problem, demonstrating the effectiveness of the multi-start metaheuristic algorithm and the improvement achieved by the matheuristic approach. Additionally, a benchmark instance set is proposed for standardized computational comparisons in future works.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2021)
Article
Operations Research & Management Science
Manoel Campelo, Jhonata A. S. Matias
Summary: The problem of minimizing the maximum flow degree in an arc-capacitated network is studied, and a polynomial time algorithm is proposed. Improved upper bounds for the flow coloring problem are derived using the algorithm's optimum value, leading to the design of an approximation algorithm that enhances the best known approximation factor.
ANNALS OF OPERATIONS RESEARCH
(2022)
Article
Computer Science, Software Engineering
Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, Mingxian Zhong
Summary: In this paper, the complexity of k-coloring in H-free graph classes is studied, where a polynomial-time algorithm is provided along with a proof that the problem is NP-hard.
Article
Mathematics, Applied
B. S. Panda, Priyamvada
Summary: This paper discusses the injective coloring problem of graphs, proving its NP-completeness for various subclasses of bipartite graphs. The difficulty of approximating the injective chromatic number of certain bipartite graphs is also highlighted. Additionally, efficient algorithms for determining the injective chromatic number of different types of graphs, such as biconvex bipartite graphs and proper interval graphs, are proposed. The complexity of the injective coloring problem for chordal graphs and split graphs is also addressed.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Interdisciplinary Applications
Zhe Sun, Una Benlic, Mingjie Li, Qinghua Wu
Summary: Investigated the application of the minimum load coloring problem in broadcast WDM networks and proposed an integer programming model and a reinforcement learning based tabu search algorithm to effectively solve the problem.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Mathematics
Tatiana Makarovskikh, Anatoly Panyukov
Summary: This article investigates routing problems for plane graphs to solve control problems of cutting machines in the industry. By analyzing the solvability of the routing problems in the graph, the authors propose polynomial algorithms to obtain routes with the minimum number of covering paths and the minimum length of transitions. The solutions presented in this article can improve the quality of technological preparation of cutting processes in CAD/CAM systems.
Article
Computer Science, Software Engineering
Kazuya Shimizu, Ryuhei Mori
Summary: This article presents two quantum algorithms. One uses quantum random access memory (QRAM) to compute the chromatic number of a graph with a running time of O(1.9140(n)). The other is a polynomial-space quantum algorithm for the 20-coloring problem in graphs, with a running time of O(1.9575(n)) and does not use QRAM.
Article
Management
Jisun Lee, Seulgi Joung, Kyungsik Lee
Summary: The paper discusses a probability maximizing shortest path problem, proving its difficulty in certain scenarios and proposing an approximation scheme that can be applied to similar combinatorial optimization problems.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Interdisciplinary Applications
Daniel Yamin, Andres L. Medaglia, A. Arun Prakash
Summary: This paper proposes a method to solve the problem of finding the least expected travel-time path on stochastic and time-dependent networks. By extending the pulse algorithm and introducing various strategies, the solution approach is accelerated. Experimental results show that the algorithm performs favorably compared to existing methods on real-world transportation networks.
COMPUTERS & OPERATIONS RESEARCH
(2022)
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)
