Article
Computer Science, Hardware & Architecture
Hongbin Zhuang, Xiao-Yan Li, Jou-Ming Chang, Cheng-Kuan Lin, Ximeng Liu
Summary: This article proposes the concept of the partitioned fault model and explores the fault tolerability of interconnection networks using novel indicators. The research results demonstrate the optimality of these indicators in terms of the number of edge faults tolerated.
IEEE TRANSACTIONS ON COMPUTERS
(2023)
Article
Mathematics, Applied
Huifeng Zhang, Xirong Xu, Ziming Wang, Qiang Zhang, Yuansheng Yang
Summary: This paper focuses on the fault-tolerant Hamiltonian connectivity of the augmented cube AQ(n) and proves properties related to weak vertex-pairs and fault-free Hamiltonian paths in AQ(n). The paper provides an optimal and sharp result without restrictions on each vertex.
Article
Computer Science, Theory & Methods
Xirong Xu, Huifeng Zhang, Ziming Wang, Qiang Zhang, Peng Zhang
Summary: This study examines the fault-tolerant edge-pancyclicity of the n-dimensional crossed cube, showing that in some cases, at most n-2 faulty vertices and/or edges can be tolerated, with optimal results in certain senses.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2021)
Article
Computer Science, Information Systems
Weibei Fan, Jianxi Fan, Zhijie Han, Peng Li, Yujie Zhang, Ruchuan Wang
Summary: This paper mainly studies the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQ(s, t) - (f(v) + f(e)), proving that for s > 2, t > 3, and s <= t, an LeTQ(s, t) can tolerate up to s - 1 faulty vertices and edges when embedding a Hamiltonian cycle. Furthermore, it is also proven that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ(s, t) with up to (s - 2) faulty vertices and edges. The results demonstrate that LeTQ(s, t) is (s - 1)-Hamiltonian and (s - 2)-Hamiltonian-connected, achieving optimal (s - 1)-fault-tolerant Hamiltonicity and (s - 2) fault-tolerant Hamiltonian connectivity.
FRONTIERS OF COMPUTER SCIENCE
(2021)
Article
Computer Science, Theory & Methods
Ting Lan, Huazhong Lu
Summary: This paper introduces a novel interconnection network called the balanced hypercube BHn for massive parallel systems. It is proven that BHn remains Hamiltonian after deleting at most 4n - 5 faulty edges, and a Hamiltonian cycle still exists in BHn after deleting a set F of edges with | F | <= 5n - 7 if certain conditions are met. This research improves upon existing results and is of significant importance.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Information Systems
Mingzu Zhang, Wenhuan Ma, Tianlong Ma
Summary: This research explores the relationship between edge disjoint paths connecting disconnected subgraphs and the extra edge connectivity in a graph, based on the Menger theorem. By studying the augmented cube, it is observed that the extra edge connectivity exhibits a concentration behavior for exponentially large values of g, and for specific values in the cube. The exact values of the extra edge connectivity in the augmented cube are determined by specific formulas and exhibit sharp upper and lower bounds. Additionally, the study also involves finding exponential edge disjoint paths with edge faults in the augmented cube.
Article
Mathematics, Applied
Meijie Ma, Jiguo Yu
Summary: This article investigates edge-disjoint paths in augmented cubes with faulty edges, proving some important results and introducing the concept of extra edge-connectivity.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
Yuxing Yang, Lingling Zhang
Summary: The paper investigates the conditions for the existence of a Hamiltonian path in faulty k-ary n-cube networks. It is proven that a Hamiltonian path exists through a linear forest in the network when the paths in the linear forest do not have the target nodes as internal or end nodes.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2022)
Article
Computer Science, Hardware & Architecture
Lina Ba, Hailun Wu, Heping Zhang
Summary: This research explores the connectivity parameter of networks and introduces the concepts of structure connectivity and substructure connectivity of graphs. By computing the specific structure connectivity of n-dimensional folded hypercubes and augmented cubes, improved results are obtained compared to existing findings.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Computer Science, Theory & Methods
Xiao-Yan Li, Kun Zhao, Hongbin Zhuang, Xiaohua Jia
Summary: This paper focuses on the fault tolerance of networks in the presence of Hamiltonian paths and cycles and explores the existence of such paths and cycles in balanced hypercubes with exponentially faulty edges. The author proposes three measures and shows that the BHn is fault-tolerant for n >= 2. The comparison results demonstrate that the partitioned fault model provides exponential fault tolerance as the dimension n grows.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2023)
Article
Computer Science, Theory & Methods
Hongbin Zhuang, Xiao-Yan Li, Jou-Ming Chang, Dajin Wang
Summary: This paper proposes an efficient fault-tolerant Hamiltonian path embedding algorithm for enhancing the fault-tolerant capacity of k-ary n-cubes. A new conditional fault model named Partitioned Edge Fault model (PEF model) is introduced. Experimental and comparative results show that the algorithm significantly improves the edge fault tolerance compared to known results.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Hardware & Architecture
Kung-Jui Pai, Ro-Yu Wu, Sheng-Lung Peng, Jou-Ming Chang
Summary: This paper investigates the construction of multiple edge-disjoint Hamiltonian cycles (EDHCs) in a crossed cube network and evaluates the performance of data broadcasting. The results show that multiple EDHCs can be constructed in the crossed cube network, significantly improving the success rate and latency of edge fault-tolerant data broadcasting.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Computer Science, Theory & Methods
Eddie Cheng, Laszlo Liptak, Ke Qiu, Zhizhang Shen, Abhishek Vangipuram
Summary: This paper presents upper bounds for the g-extra connectivity of the augmented hypercube structure, studies its lower bound through the super connectedness property, and suggests an asymptotically tight bound.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Hardware & Architecture
Yunxia Ren, Shiying Wang
Summary: In this paper, we investigate the diagnosability of a class of Cayley graphs under the PMC model. We prove that even with a certain number of faulty edges, the graphs still maintain strong local diagnosability property. Additionally, we demonstrate that as long as each vertex is incident with a sufficient number of fault-free edges, the graphs maintain strong local diagnosability, regardless of the number of faulty edges.
Article
Computer Science, Theory & Methods
Hongwei Qiao, Jixiang Meng
Summary: In this study, we investigate the two-disjoint-cycle-cover vertex pancyclicity of augmented cubes and show that the n-dimensional augmented cube AQ(n) is two-disjoint-cycle-cover vertex [3, 2(n-1)]-pancyclic for n >= 3.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Mathematics
Dong-Dong Hou, Yan-Quan Feng, Dimitri Leemans
JOURNAL OF GROUP THEORY
(2019)
Article
Computer Science, Theory & Methods
Dong-Dong Hou, Yan-Quan Feng, Dimitri Leemans
DISCRETE & COMPUTATIONAL GEOMETRY
(2020)
Article
Mathematics
Yan-Quan Feng, Istvan Kovacs, Da-Wei Yang
JOURNAL OF ALGEBRAIC COMBINATORICS
(2020)
Article
Mathematics, Applied
Dongqin Cheng
Summary: This paper investigates the restricted connectivity of n-dimensional balanced hypercubes and proves the minimum cardinality of the vertex set under certain conditions.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
Dongqin Cheng
Summary: This paper proves that in an n-dimensional locally twisted cube LTQ(n), if a set of edges P contains at most n-1 edges, then LTQ(n) contains a Hamiltonian cycle passing through every edge of P, where n >= 4. Additionally, LTQ(3) has a Hamiltonian cycle passing through at most one prescribed edge.
JOURNAL OF INTERCONNECTION NETWORKS
(2022)
Article
Computer Science, Theory & Methods
Dongqin Cheng
Summary: This paper investigates the connectivity of a specific structure of 2-dimensional torus networks. The results determine the additional connectivity, structure connectivity, and substructure connectivity of the networks under different conditions. These findings are important for assessing the fault-tolerance of the networks.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2022)
Article
Computer Science, Theory & Methods
Dongqin Cheng
Summary: This paper investigates the properties of the n-dimensional locally twisted cube LT Q(n). It is proved that for any node x in LT Q(n), there exist multiple edge-disjoint cycles that intersect with each LT Q(n-2)(alpha beta).
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Mathematics, Applied
Dongqin Cheng
Summary: The alternating group graph has been extensively studied in recent years due to its many desirable properties. This paper proves that the n-dimensional alternating group graph is panyclic with a specific disjoint-cycle-cover property for n >= 4.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Computer Science, Hardware & Architecture
Kaige Pan, Dongqin Cheng
Summary: This paper introduces the definitions of structure connectivity and substructure connectivity, and investigates star structure and star substructure connectivity of Cayley graphs generated by transposition trees.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Computer Science, Theory & Methods
Heqin Liu, Dongqin Cheng
Summary: This paper discusses the generalized 4-connectivity of FQ(n) and proves that kappa(4)(FQ(n)) is equal to n when n is greater than or equal to 7.
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY
(2022)
Article
Computer Science, Hardware & Architecture
Heqin Liu, Dongqin Cheng
Summary: In this paper, we introduce a variant of hypercube called exchanged hypercubeEH(s,t), which is obtained by removing some links from a (s+t+1)-dimensional hypercube. This graph retains many excellent properties, leading to extensive studies on its reliability and fault tolerance. By combining the concepts of structure connectivity and substructure connectivity, we establish the P(k)-path, C(2l-)-cycle, and K(1,r)-star structure connectivity and substructure connectivity ofEH(s,t) under certain conditions. Furthermore, we determine kappa(s)(EH(s,t);C-4) for 5 <= s <= t and provide an upper bound for kappa(EH(s,t);C-4) for 4 <= s <= t.
Article
Mathematics, Applied
Dongqin Cheng
Summary: This paper investigates a variant of the locally twisted cube called n-dimensional locally twisted cube and proves that its generalized 4-connectivity is n-1. This result is significant for evaluating the fault-tolerance of networks.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2023)
Article
Computer Science, Interdisciplinary Applications
Dongqin Cheng
Summary: This paper investigates the application of edge-disjoint trees in large-scale networks and proves the existence of at least two edge-disjoint trees passing through any given four vertices. The result is optimal.
JOURNAL OF COMPUTATIONAL SCIENCE
(2023)
Article
Mathematics
Heqin Liu, Dongqin Cheng
Summary: The generalized connectivity is a new criterion for measuring the fault tolerance of networks. The n-dimensional crossed cube network CQ(n) is considered as an attractive alternative to hypercube network due to its many good properties. The results of the generalized 3-connectivity and generalized 4-connectivity of CQ(n) are kappa(3)(CQ(n)) = kappa(4)(CQ(n)) = n - 1, where n >= 2.
DISCUSSIONES MATHEMATICAE GRAPH THEORY
(2022)
Article
Mathematics, Applied
Dongqin Cheng
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
(2020)
Article
Computer Science, Theory & Methods
Hoa T. Vu
Summary: This paper addresses the maximum satisfiability problem in the data stream model. It presents algorithms that achieve approximations to the optimum value and corresponding Boolean assignments in sublinear space complexity. The paper also discusses related problems and provides approximation algorithms and space complexity for them.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Sameep Dahal, Jukka Suomela
Summary: This research demonstrates that finding a maximal fractional matching in distributed graph algorithms requires the use of fine-grained fractional values, and gives a specific characterization of the small value requirements, with a denominator of at least 2d. It also provides a new algorithm to meet these requirements.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Peng Yang, Yuan Huang, Zhiguo Fu
Summary: This paper investigates the computational complexity classification of Holant problems on 3-regular graphs and provides corresponding conclusions.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Yi-Jun Chang
Summary: This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks. Recent studies have shown that some problems can be solved with energy-efficient algorithms, while others require significant energy consumption. To improve energy efficiency, this paper focuses on bounded-genus graphs and proposes corresponding algorithms.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Dekel Tsur
Summary: This paper proposes algorithms for 2-CLUB CLUSTER VERTEX DELETION and 2-CLUB CLUSTER EDGE DELETION problems. The algorithms have running times of O*(3.104k) and O*(2.562k) respectively, and were obtained using automated generation of branching rules. These results improve upon previous algorithms for the same problems.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Xianrun Chen, Sai Ji, Chenchen Wu, Yicheng Xu, Yang Yang
Summary: This paper introduces the diversity-aware fair k-supplier problem and presents an efficient 5-approximation algorithm to address the fairness and over-representation issues in facility selection.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara
Summary: Sliding block puzzles play a crucial role in computational complexity, with their complexity varying depending on the rules and set of pieces. In this study, we explore the computational complexities of jumping block puzzles, a newer concept in the puzzle community. We analyze different variants of these puzzles based on real puzzles and a natural model, and determine their complexities. Our findings show that these puzzles are generally PSPACE-complete, with additional cases being NP-complete or solvable in polynomial-time.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar
Summary: This paper studies the many-to-many bipartite matching problem with two-sided preferences and two-sided lower quotas. By defining the concept of critical matching, the goal is to find a popular matching in the set of critical matchings, and an efficient algorithm is proposed to compute a popular matching of the largest size.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Rahul Jain, Raghunath Tewari
Summary: To solve the reachability problem is to determine if there is a path between two vertices in a graph. This paper studies space-efficient algorithms that run in polynomial time to decide reachability. An algorithm is presented that solves reachability in directed graphs using O(n log n) space.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Daniel Berend, Liat Cohen, Omrit Filtser
Summary: The Tower of Hanoi puzzle has been a fascination for mathematicians and theoretical computer scientists for over a century. By using graph theory, we can study connectivity, shortest paths, and other properties of the Hanoi puzzle. Additionally, the Hanoi graphs are related to interesting structures such as the Sierpinski gasket and Gray codes.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Ling Gai, Weiwei Zhang, Zhao Zhang
Summary: This paper studies the problem of selfish bin packing with punishment. Different types of punishments are considered, and it is shown that punishment based on the result can achieve better performance with an upper bound of approximately 1.48 compared to the optimal solution.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Di Wang, Jinhui Xu
Summary: This paper studies the problem of Differentially Private Empirical Risk Minimization (DP-ERM) with both convex and non-convex loss functions. Several new methods are proposed for DP-ERM with smooth convex loss functions, achieving near-optimal expected excess risks while reducing gradient complexity. For DP-ERM with non-convex loss functions, both low and high dimensional spaces are explored, and utility measurements are introduced using different norms and error bounds. The paper reveals that certain non-convex loss functions can be reduced to a level similar to convex loss functions.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Florian Bruse, Maurice Herwig, Martin Lange
Summary: This paper presents a weight measure for formal languages based on the summands of a geometric series discounted by the fraction of words of certain length in the language. It shows that this weight measure is computable for regular languages. As an application, a distance metric between languages is derived as the weight of their symmetric difference, which can be used in automatic grading of standard exercises in formal language theory classes.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Oliver Bachtler, Tim Bergner, Sven O. Krumke
Summary: By studying the almost disjoint paths problem and the separating by forbidden pairs problem, this paper reveals that they have an unbounded duality gap and analyzes their complexity. In addition, for a fixed value of k, an efficient algorithm is proposed to solve the ADP problem.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Elisabeth Remy, Paul Ruet
Summary: This paper studies the extension of the nested canalization property to multivalued functions and investigates the effect of the Van Ham mapping on this property. The study finds that the Van Ham mapping transforms softly nested canalizing multivalued functions into nested canalization Boolean functions, a property that is also relevant in the modeling of gene regulatory networks.
THEORETICAL COMPUTER SCIENCE
(2024)
