Article
Operations Research & Management Science
Edouard Bonnet, Sergio Cabello
Summary: The research investigates the parameterized complexity of determining whether a graph G has a subset of a vertices and b edges whose removal disconnects G, or disconnects two prescribed vertices s, t from V(G).
ANNALS OF OPERATIONS RESEARCH
(2021)
Article
Mathematics, Applied
H. Naresh Kumar, D. Pradhan, Y. B. Venkatakrishnan
Summary: The paper discusses the problem of double vertex-edge domination in graphs and presents algorithms for different types of graphs. It also proves certain properties of the problem, such as its complexity for chordal graphs and the approximation factor for some cases.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2021)
Article
Mathematics, Applied
Xin Feng, Zongtian Wei, Yucheng Yang
Summary: This paper introduces a new graph parameter, edge neighbor toughness, to measure the difficulty of breaking a graph into many components through the deletion of closed neighborhoods of a few edges. The properties of this parameter are investigated, and the computational problem of edge neighbor toughness is proven to be NP-complete. Finally, a polynomial algorithm for computing the edge neighbor toughness of trees is provided.
Article
Automation & Control Systems
Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche
Summary: The paper investigates the computational complexity of finding temporally disjoint paths and walks in temporal graphs. It shows that the problem is computationally hard on general graphs, but polynomial-time solvable for certain cases.
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS
(2023)
Article
Engineering, Manufacturing
Gur Mosheiov, Daniel Oron, Dvir Shabtay
Summary: We study two NP-hard single-machine scheduling problems with generalized due-dates. In the first problem, the objective is to minimize the maximal absolute lateness, while in the second problem, the goal is to maximize the weighted number of jobs completed exactly at their due-date. Both problems are known to be strongly NP-hard regardless of the number of different due-dates in the instance. Our objective is to examine the tractability of these problems with respect to the number of different due-dates. We show that the problems remain NP-hard even when the number of different due-dates is 2, and they can be solved in pseudo-polynomial time when the value of nu(d) is bounded by a constant. Additionally, we demonstrate that both problems are fixed parameterized tractable when considering the number of different due-dates and the number of different processing times as parameters.
JOURNAL OF SCHEDULING
(2022)
Article
Mathematics
Attila Joo
Summary: For every digraph D and r ∈ V(D), the edge sets of the r-flame subgraphs of D form a greedoid. Our method provides a new proof of Lovasz's theorem, stating that there exists an r-flame subdigraph F of D such that lambda_F(r, v) = lambda_D(r, v) for v ∈ V(D) - r, along with a polynomial algorithm working with a fractional generalization of Lovasz's theorem.
JOURNAL OF GRAPH THEORY
(2021)
Article
Multidisciplinary Sciences
Zhixing Duan, Huiqin Jiang, Xinyue Liu, Pu Wu, Zehui Shao
Summary: This paper investigates the independent Roman dominating function and its decision problem of minimum weight. By proving the NP-completeness of the minimum IRDF problem in chordal bipartite graphs, we uncover the complexity difference between RDF and IRDF problems. In addition, we propose a linear-time algorithm for computing the minimum weight of an independent Roman dominating function in trees.
Article
Computer Science, Hardware & Architecture
Zhecheng Yu, Liqiong Xu
Summary: Reliability evaluation is crucial in the design and maintenance of multiprocessor systems. This study introduces more refined quantitative indicators based on edge-connectivity to assess the reliability of multiprocessor systems. The parameters of extra edge-connectivity and component edge-connectivity are extensively explored to evaluate the robustness of multiprocessor systems. The h-extra edge-connectivity and (g+1)-component edge-connectivity of balanced complete t-partite graph K-r(t) are determined in this paper, where t, r ≥ 2, 1 ≤ h ≤ Ltr/2J, and 2 ≤ g ≤ tr-1.
Article
Computer Science, Hardware & Architecture
David Harvey, Joris van der Hoeven
Summary: "Assuming a widely believed hypothesis, we show efficient algorithms for multiplication of polynomials and integers in finite fields and Turing machine model respectively."
JOURNAL OF THE ACM
(2022)
Article
Computer Science, Theory & Methods
J. Bang-Jensen, A. Yeo
Summary: This paper investigates the problems of edge connectivity and colorability of graphs, and solves the complexity problems related to them.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Mathematics
Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira, Ana Silva
Summary: Building on previous research, this paper proves that the MaxCut problem is NP-complete on permutation graphs, which settles a long-standing open problem raised by David S. Johnson in the 1985 column of the Ongoing Guide to NP-completeness.
JOURNAL OF GRAPH THEORY
(2023)
Article
Mathematics
On-Hei Solomon Lo, Jens M. Schmidt
Summary: This article presents three cut trees of graphs that provide insights into the edge-connectivity structure. The cut trees are defined based on a binary symmetric relation R on the vertex set of the graph, and they generalize Gomory-Hu trees. The article proves various properties of simple graphs and improves some lower bounds related to vertex pairs, edge-connected components, and cuts in graphs.
JOURNAL OF COMBINATORIAL THEORY SERIES B
(2024)
Article
Engineering, Geological
Maxime Lacour, Guillaume Bal, Norman Abrahamson
Summary: The method introduces new stochastic variables and orthogonal polynomials to dynamically propagate epistemic uncertainty in material properties into a finite-element system, resulting in a time-domain polynomial chaos representation of the entire finite-element solution.
INTERNATIONAL JOURNAL FOR NUMERICAL AND ANALYTICAL METHODS IN GEOMECHANICS
(2021)
Article
Operations Research & Management Science
Cuixia Miao, Fanyu Kong, Juan Zou, Ran Ma, Yujia Huo
Summary: This paper investigates the parallel-machine scheduling problem with step-deteriorating jobs. The authors prove the NP-hardness of the problem and propose a property of any optimal schedule. They also demonstrate that two special cases can be solved in polynomial time. For the problem of minimizing total weighted completion time, the authors analyze its NP-hardness and present a polynomial time optimal algorithm for certain cases.
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Engineering, Multidisciplinary
Byung-Cheon Choi, Myoung-Ju Park, Kyung Min Kim
Summary: This article investigates the min-max version of a single-machine scheduling problem with generalized due dates and processing time uncertainty. Through proving the complexity of specific cases and the existence of approximation algorithms, a practical solution approach is proposed.
ENGINEERING OPTIMIZATION
(2022)
Article
Mathematics, Applied
Zhao Wang, Yaping Mao, Yue Li, Boris Furtula
Summary: A novel topological invariant named the Sombor index was proposed recently, providing a geometric view onto graph edges. The mathematical relationships between the Sombor index and other degree-based descriptors were investigated, leading to some Nordhaus-Gaddum-type results. Computational testing and comparison with other well-established indices were presented.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2022)
Article
Mathematics
Yanling Mao, Yaping Mao
Summary: This paper discusses the analogue of the Popoviciu inequality for determinants of positive definite matrices and extends the result to sectorial matrices whose field of values are contained in a sector.
LINEAR & MULTILINEAR ALGEBRA
(2022)
Article
Computer Science, Interdisciplinary Applications
Tianlong Ma, Eddie Cheng, Yaping Mao, Xu Wang
Summary: This paper investigates the maximum fractional matching of a graph and provides some sufficient and necessary conditions to characterize it. Furthermore, it also obtains sharp lower bounds of the fractional matching number for Cartesian product, strong product, lexicographic product, and direct product.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Mathematics
Yaping Mao, Zhao Wang, Colton Magnant, Ingo Schiermeyer
Summary: Given a graph G and a positive integer k, the Gallai-Ramsey number is defined as the minimum number of vertices n such that any k-edge coloring of K-n contains either a rainbow triangle or a monochromatic copy of G. This paper obtains bounds on the Gallai-Ramsey number for wheels and the exact value for the wheel on 5 vertices.
GRAPHS AND COMBINATORICS
(2022)
Article
Mathematics, Applied
Jinyu Zou, Yaping Mao, Zhao Wang, Eddie Cheng
Summary: This paper investigates the fractional matching preclusion number of a graph, providing sharp upper and lower bounds for this number. It also characterizes graphs with large and small fractional matching preclusion numbers. Furthermore, it explores extremal problems related to the fractional matching preclusion number.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Eddie Cheng, Yaping Mao, Ke Qiu, Zhizhang Shen
Summary: This paper presents a general approach for deriving diagnosability results of various interconnection networks. Demonstrative examples are provided to show the effectiveness of this approach, and the g-extra diagnosabilities of the hypercube, the (n, k)-star, and the arrangement graph are derived. These results agree with previous findings and eliminate the need for duplicating independent technical details, with some results having a larger applicable range.
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2022)
Article
Biochemical Research Methods
Changxiang He, Yuru Liu, Hao Li, Hui Zhang, Yaping Mao, Xiaofei Qin, Lele Liu, Xuedian Zhang
Summary: This study introduces a novel Multi-Type Feature Fusion based on Graph Neural Network (MFFGNN) model for accurate prediction of drug-drug interactions (DDIs). Experimental results demonstrate the superior performance and good generalization ability of MFFGNN in DDI prediction.
BMC BIOINFORMATICS
(2022)
Article
Mathematics, Applied
Jiannan Zhou, Zhihui Li, Yaping Mao, Meiqin Wei
Summary: In this paper, the exact values or upper and lower bounds of Gallai-Ramsey number grk(G : H) and Ramsey numbers R2(H), R3(H) are determined for specific graph structures.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Yaping Mao, Kenta Ozeki, Aaron Robertson, Zhao Wang
Summary: This article investigates several functions related to the off-diagonal van der Waerden numbers and provides new lower bounds, exact values, and bounds for related numbers. It introduces the concept of Gallai-van der Waerden numbers and obtains exact values and bounds using the probabilistic method and the Lovasz Local Lemma.
JOURNAL OF COMBINATORIAL THEORY SERIES A
(2023)
Article
Mathematics
Yaping Mao, Zhao Wang, Colton Magnant, Ingo Schiermeyer
Summary: Given a graph G and a positive integer k, the Gallai-Ramsey number is defined as the minimum number of vertices n such that any edge-coloring of Kn using at most k colors contains either a rainbow triangle or a monochromatic copy of G. In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for fans Fm = K1 + mK2 and prove the sharp result for m = 2 and for m = 3 with k even.
DISCRETE MATHEMATICS
(2023)
Article
Mathematics
Jinyu Zou, Zhao Wang, Hong-Jian Lai, Yaping Mao
Summary: In this paper, the authors investigate the Gallai-Ramsey number grk(G:H), which is the minimum integer N such that every k- edge-coloring of Kn contains either a rainbow colored copy of G or a monochromatic copy of H. The authors obtain some exact values or bounds for gr(k)(P5:H) (k = 3) when H is a general graph or a star with extra independent edges or a pineapple.
GRAPHS AND COMBINATORICS
(2023)
Article
Mathematics
Hengzhe Li, Huayue Liu, Jianbing Liu, Yaping Mao
Summary: This paper investigates two conjectures about connectivity in graphs and provides proofs for certain special cases of these conjectures.
GRAPHS AND COMBINATORICS
(2023)
Article
Computer Science, Theory & Methods
Guowei Dai, Yannan Chen, Yaping Mao, Dachuan Xu, Xiaoyan Zhang, Zan -Bo Zhang
Summary: This paper addresses the perfect demand matching problem (PDM) that combines elements from the knapsack problem and the b-matching problem. The authors investigate the performance of the Max-sum belief propagation algorithm for solving PDM and provide a rigorous theoretical analysis. They establish that the algorithm can converge to the optimal solution of PDM within pseudo-polynomial time under certain conditions. This analysis is based on primal-dual complementary slackness conditions, and it is rare for the BP algorithm to be proven correct for NP-hard problems.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2023)
Article
Mathematics
Yaping Mao, Christopher Melekian, Eddie Cheng
Summary: In a connected graph G=(V, E), an S-Steiner tree is a subgraph T=(V', E') that is a tree with a vertex subset S of V(G). If each vertex of S in T has a degree of 1, it is called a pendant S-Steiner tree. Two S-Steiner trees are internally disjoint if they do not share any vertices other than S and have no common edges. The pendant tree-connectivity tau(G)(S) is the maximum number of internally disjoint pendant S-Steiner trees in G for S subset of V(G) with |S|>=2, and the k-pendant tree-connectivity tau(k)(G) is the minimum value of tau(G)(S) among all sets S with k vertices. We provide a lower bound for tau(3)(G o H), where G and H are connected graphs and o denotes the lexicographic product.
CZECHOSLOVAK MATHEMATICAL JOURNAL
(2023)
Article
Mathematics
Yaping Mao
Summary: In this paper, the concept of size Ramsey and Gallai-Ramsey numbers for graphs is introduced and their upper and lower bounds are derived. Two comparison problems are also addressed, and solutions are provided. Additionally, asymptotic lower bounds for the size Gallai-Ramsey number are obtained using the probabilistic method and Lovasz local lemma.
GRAPHS AND COMBINATORICS
(2023)
