Article
Computer Science, Theory & Methods
Chao Wei, Rong-Xia Hao, Jou-Ming Chang
Summary: This paper focuses on constructing internally disjoint S-trees with |S| = 3 in the n-dimensional augmented cube A Q(n), and completely determines the kappa(3)-connectivity of A Q(n).
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2021)
Article
Mathematics, Applied
Litao Guo, Gulnaz Boruzanli Ekinci
Summary: In this paper, a new type of network called folded twisted crossed cube FTCQ(n) is introduced, obtained from twisted crossed cube TCQ(n) by adding extra edges. The connectivity and edge connectivity of FTCQ(n) are shown to be n + 1 for n >= 4. Additionally, the super-connectivity and super-edge-connectivity of FTCQn are determined to be 2n for n >= 4.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics, Applied
Mujiangshan Wang, Shiying Wang
Summary: Connectivity and diagnosability of a multiprocessor system or an interconnection network are important research topics. This paper introduces the concepts of g-good-neighbor and g-extra diagnosability, and analyzes these measures for the center k-ary n-cube network in depth.
DISCRETE APPLIED MATHEMATICS
(2021)
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
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, Information Systems
Shu-Li Zhao, Jou-Ming Chang
Summary: The article introduces the concepts of graph G and set S, defines S-tree and internally disjoint trees, and describes the definition of generalized r-connectivity and the characteristics of the folded divide-and-swap cube.
INFORMATION PROCESSING LETTERS
(2023)
Article
Computer Science, Theory & Methods
Yuxing Yang
Summary: In this paper, the properties of t-embedded vertex connectivity and t-embedded edge connectivity in recursive networks are proved, providing conclusions for calculations under different t values.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Mathematics, Applied
Xuenan Chang, Jicheng Ma, Da-Wei Yang
Summary: This paper investigates the symmetry of the locally twisted cube LTQ(n), proving that it is different from the hypercube Q(n). The results obtained in this study provide insights into the structure of LTQ(n) and generalize some previous works on this topic.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics
Yingli Kang, Shuai Ye, Weidong Fu, Jing Zhu
Summary: Diagnosability is an important metric for measuring the reliability of multiprocessor systems. This paper investigates the diagnosability and pessimistic diagnosability of folded Petersen cubes, and derives the corresponding results.
JOURNAL OF MATHEMATICS
(2022)
Article
Mathematics, Applied
Xiaowang Li, Shuming Zhou, Xiangyu Ren, Xia Guo
Summary: Connectivity is an important indicator for evaluating network robustness. This paper investigates the H-structure connectivity and H-substructure connectivity of the alternating group graph AGn for different isomorphic cases of H, providing a calculation of connectivity values for robustness evaluation.
APPLIED MATHEMATICS AND COMPUTATION
(2021)
Article
Computer Science, Theory & Methods
Shiying Wang
Summary: This paper studies the g-extra diagnosability of the Mobius cube MQ(n) under different models and provides corresponding mathematical expressions.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Computer Science, Hardware & Architecture
Xi Wang, Jianxi Fan, Shukui Zhang, Jia Yu
Summary: This paper explores the construction of node-to-set disjoint paths in an n-dimensional cross-cube C-n, presenting an O(Nlog(2)N) algorithm and simulation results for the maximal length of disjoint paths obtained by the algorithm.
JOURNAL OF SUPERCOMPUTING
(2022)
Article
Computer Science, Theory & Methods
Yu-Huei Chang, Kung-Jui Pai, Chiun-Chieh Hsu, Jinn-Shyong Yang, Jou-Ming Chang
Summary: Completely Independent Spanning Trees (CISTs) in a network play a crucial role in protection routing configuration and network performance optimization. Some studies have shown that dual-CISTs have wide applications in intra-domain IP networks.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Mathematics
Kung-Jui Pai
Summary: This paper discusses the applications of edge-disjoint Hamiltonian cycles (EDHC) in locally twisted cubes (FLTQ) and crossed cubes (FCQ) with the center at the origin, including parallel data broadcasting and edge fault-tolerance in network communications. Three EDHCs are constructed in FLTQ(5) and FCQ(5) using the technique of edge exchange. It is proved that there are three EDHCs in FLTQ(n) and FCQ(n) when n≥6 based on their recursive structures. The data broadcasting performance of three EDHCs in FLTQ(n) and FCQ(n) is evaluated by simulation for 5≤n≤9, considering multiple faulty edges occurring randomly.
Article
Computer Science, Hardware & Architecture
Lulu Yang, Xiaohui Hua, Yuxing Yang
Summary: If removing any minimum H-structure-cut or minimum H-substructure-cut isolates a component isomorphic to M, G is considered to be super HIM-connected or super sub HIM-connected. Additionally, if removing any minimum H-structure-cut or minimum H-substructure-cut splits G into two components, one of which is isomorphic to M, G is classified as hyper HIM-connected or hyper sub-HIM-connected. The paper proves that the n-dimensional star network Sn satisfies the hyper HIK1-connected and hyper sub-H broken vertical bar K-1-connected properties for certain values of H and n.
JOURNAL OF SUPERCOMPUTING
(2023)
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
Computer Science, Hardware & Architecture
Yanze Huang, Limei Lin, Eddie Cheng, Li Xu
Summary: This paper focuses on the reliability of a multiprocessor system, with an emphasis on the component diagnosability and component connectivity of a graph. The paper proposes the r-component diagnosability of the n-dimensional alternating group graph AG(n) under the PMC model, and presents a good construction for the general r-component connectivity of AG(n) where 6 <= r <= n - 1. Theoretical analysis and simulation results show that the general r-component connectivity of AG(n) is higher than that of Q(n), D-n, and FQ(n).
Article
Computer Science, Theory & Methods
Eddie Cheng, Laszlo Liptak, Ke Qiu, Zhizhang Shen
Summary: This article discusses the importance of connectivity type measures in network analysis, particularly in analyzing vulnerability and resiliency of interconnection networks. The article studies a way to extend known results in this area by considering the structure of the resulting graph when many vertices are deleted.
JOURNAL OF INTERCONNECTION NETWORKS
(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
Mohamad Abdallah, Eddie Cheng
Summary: This paper focuses on a class of Cayley graphs generated by certain 3-cycles on the alternating group An as models for interconnection networks. The fault-Hamiltonian connectivity of these graphs is analyzed, and it is proven that these graphs are (2n - 7)-fault-tolerant Hamiltonian connected.
THEORETICAL COMPUTER SCIENCE
(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
Computer Science, Theory & Methods
Mohamad Abdallah, Eddie Cheng
Summary: This article investigates the conditional strong matching preclusion number for the pancake graph, which is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Theory & Methods
Sambhav Gupta, Eddie Cheng, Laszlo Liptak
Summary: This paper investigates the conditional fractional strong matching preclusion number for burnt pancake graphs and a subset of the class of pancake-like graphs.
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY
(2022)
Article
Mathematics, Applied
Hong Zhang, Shuming Zhou, Eddie Cheng, Sun-Yuan Hsieh
Summary: The topology of multiprocessor systems is crucial for reliability evaluation in big data analysis. By analyzing the component connectivity, the fault-tolerability of the network can be measured, and system-level diagnosis strategies can be implemented. This paper presents general characteristics of component diagnosability for regular networks and provides empirical analysis on well-known regular networks.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Xiaoqing Liu, Shuming Zhou, Eddie Cheng, Hong Zhang
Summary: With the rapid development of network technology, a multiprocessor system consisting of multiple processors and communication links plays a significant role in the big data era. The topology of a multiprocessor system greatly influences network performance and the design of a high-performance network architecture is of great importance. This paper proposes a more general class of balanced hypercubes and explores their basic properties. It also demonstrates the connectivity, super connectivity, extra connectivity, and (extra) diagnosability of these hypercubes. (c) 2022 Elsevier B.V. All rights reserved.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Hardware & Architecture
Hong Zhang, Shuming Zhou, Eddie Cheng
Summary: In this work, a novel diagnostic strategy based on cyclic connectivity, namely the cyclic diagnosability, is proposed. The cyclic diagnosability of hypercube Q(n) under the PMC model and the MM* model is investigated, and it is shown that ct(Q(n)) = 5n -10 for n = 7.
Article
Mathematics, Applied
Hong Zhang, Shuming Zhou, Eddie Cheng
Summary: This study investigates the m-restricted (edge) connectivity of the Cayley graph En, generated by G(X) with a maximum matching number h. When 1 < m < h, it is proven that the m-restricted (edge) connectivity of En is Kappa m(En) = 2m(n - 1 - m) (resp., lambda m(En) = 2m(n - 1 - m)).
DISCRETE APPLIED MATHEMATICS
(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)
Proceedings Paper
Mathematics, Applied
Eddie Cheng, Laszlo Liptak, Daniel Tian
Summary: This paper explores the concept of Extraconnectivity and computes the g-extraconnectivity of small arrangement graphs (with g <= 6). Additionally, an asymptotic result for general g is provided.
COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2020
(2022)
Proceedings Paper
Computer Science, Interdisciplinary Applications
Sambhav Gupta, Eddie Cheng, Laszlo Liptak
Summary: The paper discusses the conditional fractional strong matching preclusion number for burnt pancake graphs and a subset of pancake-like graphs.
COMPUTING AND COMBINATORICS (COCOON 2021)
(2021)
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)
