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
Cheng-Nan Lai
Summary: The study in this paper focuses on constructing m node-disjoint paths in a folded hypercube to minimize the total length and maximal length, where m <= n+1. By utilizing two specific routing functions, the construction of these paths can be efficiently carried out for odd and even routing, providing strong evidence for the effective applications of routing functions in deriving node-disjoint paths.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2021)
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
Mathematics, Applied
Meijie Ma, Chaoming Guo, Xiang-Jun Li
Summary: The paper discusses the problem of embedding internally disjoint paths in an enhanced hypercube and proves that the subgraph obtained by deleting the faulty subnetwork from the enhanced hypercube remains strong Menger connected even when the network has faults.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2023)
Article
Computer Science, Theory & Methods
Suying Wu, Jianxi Fan, Baolei Cheng, Jia Yu, Yan Wang
Summary: In this paper, the logical structure of the dragonfly network is studied, and the general and specific definitions of the network are given. The connectivity of the network under specific definition is proven, and an algorithm to find disjoint paths is proposed.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Computer Science, Theory & Methods
Huazhong Lu, Tingzeng Wu
Summary: This paper discusses the many-to-many k-disjoint path cover of a graph G and the balanced hypercube BHn, proving the existence of an unpaired many-to-many (2n-2)-disjoint path cover in BHn, while also improving existing results. The upper bound of 2n-2 is proven to be the best possible in terms of the number of disjoint paths in unpaired many-to-many k-DPC of BHn.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2021)
Article
Mathematics
Che-Nan Kuo, Yu-Huei Cheng
Summary: The reliability of large-scale networks can be compromised by various factors. Recently, it has been found that in FQ(n), even when adjacent vertices encounter errors, fault-free edges can still be embedded in cycles of various lengths. The smallest communication ring in FQ(n) is observed to be the four-cycle ring.
Article
Computer Science, Hardware & Architecture
Yuxing Yang, Xiaohui Li, Jing Li
Summary: This paper investigates the definitions of H-structure connectivity and H-substructure connectivity of a given graph G, and analyzes these connectivities for n-dimensional balanced hypercube BHn under specific restrictions.
JOURNAL OF SUPERCOMPUTING
(2021)
Article
Computer Science, Information Systems
Janusz Dybizbanski, Andrzej Szepietowski
Summary: This paper investigates hypercubes with pairwise disjoint faulty edges and proves that all other hypercubes are Hamiltonian when n >= 4, as long as there are two healthy crossing edges of different parity in each dimension.
INFORMATION PROCESSING LETTERS
(2021)
Article
Computer Science, Information Systems
Keiichi Kaneko, Antoine Bossard, Frederick C. Harris
Summary: This paper discusses the importance of the bijective connection graph and the set-to-set disjoint paths problem. It proposes an algorithm with polynomial-order time complexity for constructing disjoint paths between any pair of node sets in n-dimensional bijective connection graphs.
Article
Computer Science, Information Systems
Diego Lopez-Pajares, Elisa Rojas, Juan A. Carral, Isaias Martinez-Yelmo, Joaquin Alvarez-Horcajo
Summary: The paper presents an algorithm that addresses the scalability issues in multipath communication by efficiently discovering multiple disjoint paths while maintaining bounded computational cost and ensuring scalability.
The proposed algorithm has been validated through theoretical analysis and exhaustive experimental evaluation, showing significantly higher efficiency in obtaining disjoint paths compared to competitors.
Article
Computer Science, Theory & Methods
Xiaowang Li, Shuming Zhou, Xia Guo, Tianlong Ma
Summary: This paper investigates the h-restricted connectivity of the generalized hypercube and provides a mathematical expression and calculation method for it. The research aims to more accurately evaluate the reliability and fault-tolerant ability of interconnection networks.
THEORETICAL COMPUTER SCIENCE
(2021)
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
Computer Science, Hardware & Architecture
Shiying Wang, Xiaolei Ma
Summary: This paper investigates the matching preclusion number and the strong matching preclusion number of the enhanced hypercube, providing specific values for each.
Article
Quantum Science & Technology
Michael Beverland, Vadym Kliuchnikov, Eddie Schoute
Summary: This article presents an efficient algorithm for compiling quantum circuits for fault-tolerant execution. By embedding qubits in surface codes, long-range operations can be performed in constant depth. This approach also addresses the edge-disjoint path problem. The proposed EDPC algorithm outperforms other compilation methods in terms of circuit depth and demonstrates improvement over sequential Pauli-based compilation for certain circuits.
Article
Engineering, Mechanical
Yong Xu, Yongge Li, Di Liu
NONLINEAR DYNAMICS
(2016)
Article
Mechanics
Xiufeng Xie, Junlin Li, Di Liu, Rong Guo
Article
Acoustics
Di Liu, Yong Xu, Junlin Li
JOURNAL OF SOUND AND VIBRATION
(2017)
Article
Engineering, Mechanical
Di Liu, Mei Li, Junlin Li
NONLINEAR DYNAMICS
(2018)
Article
Engineering, Mechanical
Yong Xu, Qi Liu, Guobin Guo, Chao Xu, Di Liu
NONLINEAR DYNAMICS
(2017)
Article
Mathematics, Applied
Di Liu, Jing Li, Yong Xu
COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION
(2014)
Article
Acoustics
Yong Xu, Hua Wang, Di Liu, Hui Huang
JOURNAL OF VIBRATION AND CONTROL
(2015)
Article
Acoustics
Dongmei Huang, Wei Xu, Di Liu, Qun Han
JOURNAL OF VIBRATION AND CONTROL
(2016)
Article
Engineering, Multidisciplinary
Di Liu, Yanru Wu, Xiufeng Xie
MATHEMATICAL PROBLEMS IN ENGINEERING
(2018)
Article
Engineering, Mechanical
Di Liu, Wei Xu, Yong Xu, Jing Li
NONLINEAR DYNAMICS
(2014)
Article
Mathematics, Interdisciplinary Applications
Di Liu, Yong Xu
INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS
(2019)
Article
Mathematics, Interdisciplinary Applications
Di Liu, Junlin Li, Yu Meng
CHAOS SOLITONS & FRACTALS
(2019)
Article
Engineering, Mechanical
Di Liu, Yanru Wu, Yong Xu, Jing Li
MECHANICAL SYSTEMS AND SIGNAL PROCESSING
(2019)
Article
Mathematics, Interdisciplinary Applications
Di Liu, Yong Xu, Junlin Li
CHAOS SOLITONS & FRACTALS
(2017)
Article
Engineering, Mechanical
Yong Xu, Yongge Li, Di Liu
JOURNAL OF COMPUTATIONAL AND NONLINEAR DYNAMICS
(2014)
Article
Computer Science, Information Systems
Andre Nies, Frank Stephan
Summary: We investigate word automaticity for nilpotent groups of class 2 with prime exponent p. It is proven that the infinitely generated free group in this category is not word automatic. However, the infinite extra-special p-group Ep and an intermediate group Hp with an infinite center are both word automatic. Additionally, a method for demonstrating automaticity of central extensions of abelian groups via co-cycles is introduced.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Chik How Tan, Theo Fanuela Prabowo
Summary: This paper presents a new key recovery attack on a Hamming-metric code-based signature scheme proposed by SHMWW. The attack extends the statistical part of the attack proposed by ABDKPS. In addition to classifying the columns of the secret matrix, the attack also determines the entries of the identity columns of this matrix via statistical method. The attack has better time complexity and can recover the secret key in under 45 minutes with no more than 1500 signatures.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Julio Araujo, Victor Campos, Darlan Girao, Joao Nogueira, Antonio Salgueiro, Ana Silva
Summary: This paper studies the parameter hull number in a graph convexity called Cycle Convexity, which is motivated by related notions in Knot Theory. The authors define the interval function and investigate the properties and computational methods of the minimum convex set for a graph G.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Takuto Mitsunobu, Reiji Suda, Vorapong Suppakitpaisarn
Summary: The investigation on the approximation ratio of the longest processing time (LPT) scheduling algorithm has been conducted in various studies. While the ratio is known for identical processors, it remains unknown for processors with different speeds. This study provides a tight approximation ratio for three, four, and five processors, showing that the ratios are no larger than the lower bound provided by Gonzalez et al. (1977) [14]. The ratios are approximately 1.38, 1.43, and 1.46 for three, four, and five processors, respectively.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Nidia Obscura Acosta, Alexandru I. Tomescu
Summary: This paper presents a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. The characterization is based on a simple condition of when two edges must appear consecutively in all Eulerian circuits, in terms of cut nodes of the underlying undirected graph of G. Additionally, the paper proposes a method to compute all maximal safe walks appearing in all Eulerian circuits in linear time.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Dar-Li Yang, Yung-Tsung Hou, Wen-Hung Kuo
Summary: The research states that the single-machine makespan minimization problem can be solved as an assignment problem in O(n3) time. Subsequent research shows that if the job-dependent learning effects are correlated with the level of sophistication of the jobs and have a lower bound, the scheduling problem can be solved in O(nlogn) time by sequencing the jobs according to the shortest processing time rule. The SPT job sequence remains optimal when the job-dependent learning effects are inversely correlated with the level of sophistication and have an upper bound. The main results of the paper are correct, but there are errors in Corollary 1 and incomplete proofs for Proposition 1 and Corollary 1. This note provides a counter example for the latter case and a modified corollary. A lemma is presented to complete the proofs for Proposition 1 and Corollary 1. Finally, a simple algorithm is developed to solve the latter case in O(n2) time.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Maximilien Mackie
Summary: This research investigates encodings for modular arithmetic in the lambda-calculus. Two approaches are considered: adapting existing numeral systems and creating a new one. The focus of this paper is to provide original techniques for encoding modular arithmetic directly. A modular arithmetic numeral system is presented, complete with multiplication and an implementation of the Chinese remainder theorem, all without recursion i.e., without using fixed-point operators.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Yogesh Dahiya, K. Vignesh, Meena Mahajan, Karteek Sreenivasaiah
Summary: We demonstrate that polynomial-size constant-rank linear decision trees (LDTs) can be transformed into polynomial-size depth-2 threshold circuits LTF o LTF. An intermediate structure is polynomial-size decision lists that refer to a conjunction of a fixed number of linear threshold functions (LTFs); we prove that these are equivalent to polynomial-size exact linear decision lists (ELDLs), which query precise threshold functions (ELTFs).
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Bhisham Dev Verma, Rameshwar Pratap, Manoj Thakur
Summary: Count sketch is a popular sketching algorithm used for frequency estimation in data streams and pairwise inner product for real-valued vectors. This paper extends count sketch and introduces a higher-order count sketch algorithm, which compresses input tensors to approximate the queried features. It is shown that the higher-order count sketch can also closely approximate the pairwise inner product and provides a concentration analysis of the estimate.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Jean Lienardy, Frederic Lafitte
Summary: OCB3 is an authenticated encryption mode of operation that allows for associated data (AEAD), and it is known for its maturity and provable security. However, this note highlights a small flaw in the security proof of OCB3 that can result in a loss of security when using short nonces. This flaw has implications worse than nonce-repetition, as it compromises confidentiality and authenticity until the key is changed. Various approaches to fix this flaw in OCB3 are presented.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Majid Mirzanezhad
Summary: This paper proposes the first data structure for curves under the (continuous) Frechet distance in higher dimensions, which can efficiently report all curves with distances less than a given value to a query curve. For a given k value in the preprocessing stage, we propose a deterministic data structure that can answer (1 + epsilon)delta-ANNS queries in O (kd) query time, where D is the diameter of P.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Je Hong Park, Woo-Hwan Kim
Summary: This paper revisits Zhu et al.'s attack on a certificate-based proxy signature scheme proposed by Verma et al., and shows that the fundamental problem of Verma et al.'s scheme lies in its use of a weak ordinary signature scheme. Furthermore, the paper demonstrates that the attack against Verma et al.'s scheme can be similarly applied to the revised scheme, as they share many components using the weak signature.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Lluis Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho
Summary: This study focuses on two variants of the Maximum Linear Arrangement problem, namely the planar variant for free trees and the projective variant for rooted trees. Linear time and space complexity algorithms are presented to solve these two problems. Additionally, properties of maximum projective and planar arrangements are proven, and it is shown that caterpillar trees maximize planar MaxLA among all trees of a fixed size, thereby generalizing a previous extremal result on trees.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Mislav Blazevic, Stefan Canzar, Khaled Elbassioni, Domagoj Matijevic
Summary: This paper studies the Tai mapping and anti Tai mapping problems between rooted labeled trees. For unordered trees, finding the maximum-weight Tai mapping is proven to be NP-complete. The paper provides an efficient algorithm for finding the maximum-weight anti Tai mapping and presents a polynomial computable lower bound for the optimal anti Tai mapping based on special conditions.
INFORMATION PROCESSING LETTERS
(2024)
Article
Computer Science, Information Systems
Xiaowei Li, Xiwen Lu
Summary: The facility location problem with maximum distance constraint is investigated and a (3,1)-approximation algorithm is proposed. The algorithm is compared with the previous one and is found to have lower memory requirements and is suitable for large-scale problems.
INFORMATION PROCESSING LETTERS
(2024)