Article
Computer Science, Theory & Methods
Yihong Wang, Jianxi Fan, Xueli Sun, Baolei Cheng, Yan Wang
Summary: The paper discusses the connectivity, diagnosability, and conditional diagnosability of networks based on structure faults, determining the minimum number of faulty vertices for network failure and identifying faulty vertices without replacement. Different models and variants of hypercubes are analyzed to evaluate fault-tolerability of networks, showing significant improvements in diagnosability under certain conditions.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2022)
Article
Computer Science, Theory & Methods
Hong Zhang, Jixiang Meng
Summary: The paper discusses fault diagnosis measures for multiprocessor systems proposed by Lai et al. and Zhang et al. in 2005 and 2017 respectively. The study focuses on the g-extra conditional diagnosability of graphs under different models and also examines the conditional diagnosability of DQ(m, d, n) systems. Additionally, the research determines the values of kappa(1)(DQ(m, d, n)) and kappa(2)(DQ(m, d, n)).
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2021)
Article
Computer Science, Hardware & Architecture
Shurong Zhang, Dongyue Liang, Lin Chen, Ronghua Li, Weihua Yang
Summary: This paper investigates the diagnosability of networks, defines and studies the g-component diagnosability, and provides specific calculation formulas and models.
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
Xianyong Li, Jiaming Huang, Yajun Du, Yongquan Fan, Xiaoliang Chen
Summary: Processor fault diagnosis aims to identify faulty processors in a multicomputer system, ensuring high reliability and availability. The g-good-neighbor conditional diagnosability is a novel method for fault diagnosis in various networks. The diagnostic capabilities of hypermesh optical interconnection networks are determined under the PMC model and comparison model, and the results are applied to derive the diagnosability of hypercubes under the PMC and comparison models.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2023)
Article
Mathematics, Applied
Yunxia Ren, Shiying Wang
Summary: This paper explores the diagnosability of a multiprocessor system based on a bipartite graph, considering both unconditional and conditional faulty edges. The study highlights the importance of maintaining strong local diagnosability properties under various fault scenarios.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Hardware & Architecture
Ting Tian, Shumin Zhang, Yalan Li
Summary: Diagnosability is an important metric for fault diagnosis in multiprocessor systems. Previous studies only focused on vertex faults, but we considered edge faults as well and obtained the h-edge g-good-neighbor conditional diagnosability of n-dimensional star graphs under the PMC and MM* models.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Computer Science, Hardware & Architecture
Jun Yuan, Aixia Liu, Xi Wang
Summary: The study introduces a new measurement for fault diagnosis in interconnection networks, called g-extra diagnosability, investigating various networks' g-extra diagnosability under the MM* model and proposing a general approach to derive the g-extra diagnosability from the g-extra connectivity. Additionally, a new relationship between the g-extra connectivity and the g-extra diagnosability of networks is proposed based on existing shared practices.
Article
Computer Science, Theory & Methods
Xuemin Wu, Liqiong Xu
Summary: This paper obtains the connectivity and conditional diagnosability of enhanced hypercube network based on structure faults.
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Theory & Methods
Yihong Wang, Cheng-Kuan Lin, Qianru Zhou, Shuming Zhou
Summary: The paper discusses the importance of g-good-neighbor conditional diagnosability and R-g-conditional diagnosability in network diagnosis, presenting some conclusions and lower bounds for the corresponding models.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Computer Science, Hardware & Architecture
Hong Zhang, Jixiang Meng
Summary: This paper investigates the connectivity and conditional diagnosability of DQcube network, providing mathematical formulas for them and analyzing and comparing them under different models.
Article
Automation & Control Systems
Zhaoqi Liu, Haitao Li
Summary: This paper focuses on the identification and stabilization of faulty Boolean control networks (BCNs) subject to stuck-at fault and bridging fault. It uses the semi-tensor product (STP) of matrices as the mathematical tool to determine the algebraic formulation of faulty BCNs. By constructing invariant sets corresponding to the faulty nodes, the relations between these two faults and state transition matrices are presented, which helps identify the faulty nodes. In addition, several new criteria for the robust stabilization of BCNs subject to these two faults are discussed. Finally, the obtained results are applied to analyze the stabilization of oxidative stress response pathways.
JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS
(2023)
Article
Computer Science, Theory & Methods
Jun Yuan, Ying Li, Aixia Liu, Huijuan Qiao
Summary: This paper introduces the definitions of non-inclusive g-good-neighbor diagnosability t(Ng)(G) and R-g-conditional diagnosability t(Rg)(G), and explores their relationships under different network structures. The research findings show that, under certain conditions, the non-inclusive g-good-neighbor diagnosability is less than the R-g-conditional diagnosability.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Mathematics
Meirun Chen, Cheng-Kuan Lin
Summary: This paper investigates the classical diagnosability of the generalized Cartesian product of networks (GCPNs) under the PMC model and the MM* model, and determines the accurate value of its diagnosability.
Article
Mathematics, Applied
Mei-Mei Gu, Rong-Xia Hao, Yan-Quan Feng, Erling Wei
Summary: The paper examines the conditional diagnosability of Cayley graphs generated by transposition generating graphs and discusses the conditional diagnosability under the MM* and PMC models.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Information Systems
Xin Zhang, Jingfen Lan, Bi Li, Qiang Zhu
INFORMATION PROCESSING LETTERS
(2018)
Article
Computer Science, Theory & Methods
Qiang Zhu, Lili Li, Sanyang Liu, Xing Zhang
THEORETICAL COMPUTER SCIENCE
(2019)
Article
Mathematics, Applied
Q. Zhu, J. Zhang, L. L. Li
DISCRETE APPLIED MATHEMATICS
(2018)
Article
Computer Science, Theory & Methods
Nianpeng Zhang, Qiang Zhu
Summary: This paper investigates the reliability and diagnosis capability of exchanged hypercubes, focusing on their fault tolerance ability and diagnosability under the hybrid diagnosis model. By studying the extra connectivity and restricted diagnosability of EH(s, t), we can assess its performance in fault circumstances.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Mathematics, Applied
Qiang Zhu, Fang Ma, Guodong Guo, Dajin Wang
Summary: Connectivity of a graph refers to the minimum number of nodes whose removal will disconnect the graph, serving as a metric of the graph's robustness. Conditional connectivity has been proposed to more realistically reflect a graph's robustness, with extra connectivity being a form of this concept. This paper introduces a new approach to find the extra connectivity of hypercubes and establishes a relationship between isoperimetric inequalities and the extra connectivity of graphs.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
Qiang Zhu, Krishnaiyan Thulasiraman, Kshirasagar Naik, Sridhar Radhakrishnan, Min Xu
Summary: This paper introduces a new testing model called the symmetric PMC (SPMC) model, and proves that the diagnosability of an n-dimensional hypercube under the SPMC model is almost twice its diagnosability under the PMC model. Additionally, it shows that the fault diagnosis problem for a t-diagnosable system under the SPMC model reduces to determining a maximum weighted b-matching in its diagnosis graph.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Engineering, Electrical & Electronic
Li Gen, Zhu Qiang
Summary: A microclimate detection system based on wireless sensor network was proposed to study the impact of urban spatial configuration on residential microclimate. Mathematical models were established to analyze the relationship between spatial pattern parameters and microclimate parameters, showing that building density and average height were positively correlated with microclimate parameters, while horizontal and vertical layout were negatively correlated.
IEEE SENSORS JOURNAL
(2021)
Article
Computer Science, Theory & Methods
Nianpeng Zhang, Qiang Zhu
Summary: This paper proposes the HPMC model to address the fault diagnosis problem in hybrid fault circumstances, and provides a more precise characterization of the hybrid fault diagnosis capability of multiprocessor systems by studying the h-restricted vertex diagnosability and r-restricted edge diagnosability.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Computer Science, Theory & Methods
Bi Li, Jingfen Lan, Wantao Ning, Yongcui Tian, Xin Zhang, Qiang Zhu
Summary: The paper introduces a novel generalized connectivity that combines h-extra connectivity and r-component connectivity. The h-extra r-component connectivity of n-dimensional hypercube Q(n) is also determined for r is an element of {2,3, 4}.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Mathematics, Applied
Lili Li, Xing Zhang, Qiang Zhu, Yiguang Bai
Summary: Diagnosis and diagnosability of interconnection networks are important research areas. This paper introduces a new measure of diagnosability and determines the 3-extra conditional diagnosability of n-dimensional balanced hypercubes based on their structural properties.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Operations Research & Management Science
Mei-Jie Ma, Min Xu, Tong-Tong Ding, Xiang-Jun Li, Qiang Zhu
Summary: This paper discusses the diagnosability of a multiprocessor system and system-level diagnosis strategy. Based on a sound assumption, a new diagnosability called non-inclusion diagnosability is proposed and its value is proven under a specific model. By limiting the size of the faulty set, one-step diagnosis can be achieved.
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA
(2022)
Article
Computer Science, Theory & Methods
Yongcui Tian, Qiang Zhu
Summary: This paper highlights the importance of fault diagnosability evaluation for interconnection networks and introduces various parameters to assess the fault diagnosis capability. The authors also extend previous research by determining the r-component diagnosability of hypercubes under the PMC model and studying its relationship with component connectivity.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Mathematics, Applied
Qiang Zhu, Krishnaiyan Thulasiraman, Min Xu, Sridhar Radhakrishnan
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS
(2020)
Article
Computer Science, Theory & Methods
Tongtong Ding, Min Xu, Qiang Zhu
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2020)
Proceedings Paper
Engineering, Electrical & Electronic
Qiang Zhu, Jing Chen, Lili Li
PROCEEDINGS FIRST INTERNATIONAL CONFERENCE ON ELECTRONICS INSTRUMENTATION & INFORMATION SYSTEMS (EIIS 2017)
(2017)
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)