Article
Mathematics
Junzhen Wang, Jinyu Zou, Shumin Zhang
Summary: This article introduces the important measurement of network connectivity and provides a generalized definition of connectivity. It also proves that the generalized 4-connectivity of the hierarchical star network is equal to n - 1.
Article
Mathematics, Applied
Jia Guo, Mei Lu, Xin Wang
Summary: This paper investigates the (strong) structure connectivity and (strong) substructure connectivity of the (n, k)-bubble-sort network B-n, B-k, where the special structures are complete graphs. The study evaluates the fault tolerance and reliability of the network by focusing on its special structures.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Computer Science, Theory & Methods
Kai Feng
Summary: The (n, k)-star graph is introduced and its application in building multiprocessor systems is discussed. A series of conclusions related to the number of faulty vertices in the graph and its subgraphs are derived through mathematical proofs.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(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
Mathematics, Applied
Jing Wang, Zuozheng Zhang, Yuanqiu Huang
Summary: The generalized k-connectivity of a graph G is the minimum number of internally edge disjoint S-trees, where S is any subset of the vertex set of G with |S|=k. It is an extension of classical connectivity and is crucial in applications involving modern interconnection networks. This paper investigates the generalized 3-connectivity of BPn and EA(n) and proves that kappa(3) (BPn) = n-1 for n ≥ 2, and kappa(3)(EA(n)) = n-1 for n ≥ 3.
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS
(2023)
Article
Computer Science, Hardware & Architecture
Lina Ba, Yaxian Zhang, Heping Zhang
Summary: This paper investigates the P-t-structure connectivity and P-t-substructure connectivity of augmented k-ary n-cubes AQ(n,k). The minimum connectivity for these graphs is obtained under certain conditions.
Article
Mathematics, Applied
Xiang-Jun Li, Xue-Qian Zeng, Jun-Ming Xu
Summary: This paper investigates the significance of R-h-restricted connectivity and UKappa;(h) in estimating the reliability of large-scale processor systems, and provides a formula for calculating &UKappa;(h) (A(n, 2)) in the arrangement graph A(n,k).
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Computer Science, Theory & Methods
Chai Shu, Xiang-Jun Li, Meijie Ma
Summary: Reliability analysis is crucial for the design of large multiprocessor systems, particularly in evaluating the connectivity of interconnection networks. The h-extra connectivity, represented as kh(G), refers to the minimal number of vertices needed to disconnect the network G while each remaining component still contains more than h vertices. This paper determines the h-extra connectivity of the star graph Sn for n >= 4 and 2 <= h <= 5.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Mathematics
Yali Lv, Cheng-Kuan Lin, Lantao You
Summary: BCube is a main data center network that possesses attractive features. In practical applications, component failures and physical connection failures are inevitable, especially for switch failures in data center networks. Fault-tolerance capability is a primary aspect to measure the network performance. Connectivity, fault tolerance Hamiltonian connectivity, and fault tolerance Hamiltonicity are important parameters for assessing network fault tolerance. The distribution of fault elements is typically scattered, and it is necessary to consider fault element distribution in different dimensions. This study investigates the fault tolerance of BCube when considering faulty switches and faulty links/edges that distribute in different dimensions. We also examine connectivity, fault tolerance Hamiltonian connectivity, and Hamiltonicity. This research provides a better evaluation of the fault-tolerant performance of data center networks.
Article
Mathematics, Applied
Na Wang, Jixiang Meng, Yingzhi Tian
Summary: This paper investigates the structural connectivity problem of the modified bubble-sort graph, determines the least cardinality of connected subgraphs for different cases, and proves the sharpness of these upper bounds for specific parameter values.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Mathematics, Applied
Shu-Li Zhao, Rong-Xia Hao, Jie Wu
Summary: This paper focuses on the generalized 4-connectivity of the hierarchical cubic network HCNn and shows that kappa(4)(HCNn) = n for n >= 3. As a corollary, it is also obtained that kappa(3)(HCNn) = n for n >= 3.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics, Applied
Meijie Ma, Xiang-Jun Li, Guijuan Wang, Yongli Zan
Summary: Fault-tolerance is an important indicator for measuring the stability of the interconnection network. This study fills the gap in the g-extra connectivity of the enhanced hypercube for specific cases, and derives specific results.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Jia Guo, Mei Lu
Summary: The paper discusses the impact of connectivity and edge connectivity of interconnection networks on fault tolerance. Through mathematical models and definitions, the concepts of strong Menger edge connectivity and m-edge fault tolerance are explored, with BSn serving as a specific example for analysis and verification.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
Hui Zhang, Rong-Xia Hao, Xiao-Wen Qin, Cheng-Kuan Lin, Sun-Yuan Hsieh
Summary: This paper investigates the applications of matroidal connectivity and conditional matroidal connectivity in alternating group graphs and proves the connectivity under certain conditions. The experimental results show that the matroidal connectivity significantly improves the fault-tolerant capability of alternating group graphs.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Information Systems
Yuxing Yang
Summary: This paper investigates the minimum value of t-embedded edge connectivity in n-dimensional recursive networks and the edge connectivity of k-ary n-cubes. By generalizing existing results, the edge connectivity of two formulas has been proven. This study is important for understanding interconnection networks in parallel computer systems.
INFORMATION PROCESSING LETTERS
(2023)
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)
