Article
Mathematics
Dandan Fan, Xiaofeng Gu, Huiqiu Lin
Summary: The spanning tree packing number tau(G) of a graph G is the maximum number of edge-disjoint spanning trees contained in G. The study of tau(G) is a classic problem in graph theory. This paper further extends previous results and proves tight sufficient conditions for tau(G)>= k, as well as characterizes extremal graphs. Additionally, the paper confirms a conjecture on characterizing graphs with the maximum spectral radius, and discusses applications in rigidity and nowhere-zero flows. The paper concludes with some open problems.
JOURNAL OF GRAPH THEORY
(2023)
Article
Computer Science, Hardware & Architecture
Tzu-Liang Kung
Summary: This article is dedicated to establishing a deep analysis on the exact formula of super path-connectivity for the crossed cube interconnection network. A sufficient and necessary condition is presented to classify whether or not crossed cubes can be super path-connected.
JOURNAL OF SUPERCOMPUTING
(2022)
Article
Mathematics, Applied
Jiang Zhou, Changjiang Bu, Hong-Jian Lai
Summary: This paper provides bounds on the spanning tree packing number and the arboricity of graphs in terms of effective resistances, offering a calculation method. Applications demonstrate that equiarboreal graphs are uniformly dense and determine the maximum number of edge-disjoint spanning c-forests of equiarboreal graphs. Furthermore, the arboricity of a regular graph can be directly derived from the effective resistance bounds provided.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics, Applied
Hongwei Qiao, Eminjan Sabir, Jixiang Meng
Summary: Embedding cycles into network topology is crucial for network simulation, especially embedding Hamiltonian cycles for well-designed interconnection networks.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Lantao You, Jianfeng Jiang, Yuejuan Han
Summary: This paper investigates the super spanning connectivity of the folded divide-and-swap cube (FDSCn) where n=2d and d = 1. The research shows that the super spanning connectivity of FDSCn is d+2, meaning that there exists an m-disjoint path cover (m-DPC) between any pair of nodes in FDSCn for all 1≤m≤d+2.
Article
Computer Science, Hardware & Architecture
Yujie Zhang, Weibei Fan, Zhijie Han, Yunfei Song, Ruchuan Wang
Summary: The study proposes a fault-tolerant routing algorithm based on virtual network partition technology for 3-ary n-cube networks, proving its deadlock free property. It also explores constructing disjoint paths under the fault model and proposes a fault-tolerant routing algorithm based on structure faults with disjoint paths. Simulation results show significant improvements compared to previous algorithms.
JOURNAL OF SUPERCOMPUTING
(2021)
Article
Agricultural Engineering
Tiaotiao Chen, Lizhang Xu, Ho Seok Ahn, En Lu, Yanbin Liu, Rongjin Xu
Summary: This paper investigates the path planning problem for unmanned combine harvesters and finds that the semicircle turn has the shortest path length, turning time, and required turning space. It suggests using the semicircle turn in most situations and combining it with the U turn in special cases. This approach can significantly improve working efficiency and determine the minimum required turning space.
BIOSYSTEMS ENGINEERING
(2023)
Article
Computer Science, Interdisciplinary Applications
Renjie Xu, Shouwen Yao, Weiqi Gouhe, Yinghua Zhao, Siqi Huang
Summary: This study proposes a grid-based spanning tree with adaptive pruning (STAP) algorithm for complete coverage path planning in irregularly shaped regions. Experiments show that the algorithm can plan paths with the lowest redundant coverage rate in both unobstructed and obstructed regions.
COMPUTERS & INDUSTRIAL ENGINEERING
(2023)
Article
Computer Science, Theory & Methods
Guo Chen, Baolei Cheng, Dajin Wang
Summary: This article discusses the importance and applications of constructing Completely Independent Spanning Trees (CISTs) in a network, especially in data center networks. It also introduces the augmented cube AQn as the underlying structure of a data center network and studies how to construct n-1 optimal CISTs in its logic graph L-AQDNn. Additionally, the relationship between the dimension of a hypercube-family network and the number of CISTs it can host is established for the first time.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2021)
Article
Computer Science, Artificial Intelligence
Prem Prakash Vuppuluri, Patvardhan Chellapilla
Summary: This article presents a two-phase memetic algorithm for the BDMST problem that combines a specialized recombination operator with good heuristics, showing superior solution quality and reduced computational effort in comparison to existing meta-heuristics in computational experiments.
Article
Mathematics, Applied
Xia Hong, Wei Feng
Summary: For a graph G, if there exist k spanning trees T-1, T-2, ..., T-k, such that the paths from any two vertices u, v in these k trees are pairwise openly disjoint, then these k trees are completely independent. Hasunuma proved that there are two completely independent spanning trees in any 4-connected maximal planar graph, and the problem of deciding whether there exist two completely independent spanning trees in a given graph G is NP-complete. This paper investigates the number of completely independent spanning trees in some Cartesian product graphs.
Article
Mathematics
Yuxing Jia, Mei Lu, Yi Zhang
Summary: The passage proves the edge-coloring problem of complete bipartite graphs, determining the maximum number of colors under different circumstances, and provides formulas for different scenarios.
GRAPHS AND COMBINATORICS
(2021)
Article
Chemistry, Organic
Yingui Pan, Chang Liu, Jianping Li
Summary: Polyomino systems, especially in polycyclic aromatic compounds, have been widely studied in organic chemistry. In this article, a family of molecular graphs obtained by randomly deleting some specified edges of a linear crossed polyomino chain Q(n) is constructed. Using the decomposition theorem of the Laplacian matrix characteristic polynomial, explicit formulas of Kirchhoff indices and numbers of spanning trees of these molecular graphs derived from Q(n) are obtained. Furthermore, their Kirchhoff indices are shown to be about one quarter of their Wiener indices.
POLYCYCLIC AROMATIC COMPOUNDS
(2022)
Article
Computer Science, Software Engineering
Robert Ganian, Sebastian Ordyniak
Summary: This paper revisits the classical edge-disjoint paths (EDP) problem and presents three new results that identify the role of graph structural properties in solving EDP efficiently, showing new islands of tractability in the complexity landscape of EDP.
Article
Engineering, Electrical & Electronic
Takeshi Kaneko, Kazuyuki Shudo
Summary: In a decentralized overlay network, the efficiency of broadcasts affects the performance of distributed systems. Using a spanning tree for broadcasting reduces the number of messages but results in longer routing paths. Inefficient broadcasts often occur when multiple nodes are source nodes due to different efficient tree topologies. To solve this problem, we propose a novel protocol that allows the source node to select an efficient tree from multiple spanning trees. Our method reduces routing path lengths while maintaining a small number of messages. We evaluated the performance on various topologies and found that our method significantly shortened path lengths compared to the spanning tree method, with similar message quantities.
IEICE TRANSACTIONS ON COMMUNICATIONS
(2023)
Article
Computer Science, Hardware & Architecture
Xi Wang, Alejandro Erickson, Jianxi Fan, Xiaohua Jia
Article
Computer Science, Hardware & Architecture
Yanan Chang, Xiaohua Jia, Jianqun Cui
COMPUTERS & ELECTRICAL ENGINEERING
(2015)
Article
Computer Science, Theory & Methods
Ruitao Xie, Yonggang Wen, Xiaohua Jia, Haiyong Xie
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2015)
Article
Computer Science, Theory & Methods
Baolei Cheng, Jianxi Fan, Xiaohua Jia
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2015)
Article
Computer Science, Theory & Methods
Kan Yang, Xiaohua Jia, Kui Ren
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2015)
Article
Computer Science, Interdisciplinary Applications
Marjan Marzban, Qian-Ping Gu, Xiaohua Jia
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2016)
Article
Computer Science, Information Systems
Xu Xu, Weifa Liang, Xiaohua Jia, Wenzheng Xu
WIRELESS COMMUNICATIONS & MOBILE COMPUTING
(2016)
Article
Telecommunications
Kunxiao Zhou, Liming Xie, Xiaohua Jia
WIRELESS PERSONAL COMMUNICATIONS
(2016)
Article
Computer Science, Information Systems
Weifa Liang, Wenzheng Xu, Xiaojiang Ren, Xiaohua Jia, Xiaola Lin
ACM TRANSACTIONS ON SENSOR NETWORKS
(2016)
Article
Computer Science, Information Systems
Kan Yang, Zhen Liu, Xiaohua Jia, Xuemin Sherman Shen
IEEE TRANSACTIONS ON MULTIMEDIA
(2016)
Article
Computer Science, Hardware & Architecture
Zhao Liu, Jianxi Fan, Xiaohua Jia
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
(2016)
Article
Computer Science, Information Systems
Kuai Xu, Feng Wang, Xiaohua Jia
SECURITY AND COMMUNICATION NETWORKS
(2016)
Article
Computer Science, Theory & Methods
Xi Wang, Jianxi Fan, Xiaohua Jia, Cheng-Kuan Lin
THEORETICAL COMPUTER SCIENCE
(2016)
Proceedings Paper
Computer Science, Interdisciplinary Applications
Hongwei Du, Rongrong Zhu, Xiaohua Jia, Chuang Liu
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015)
(2015)
Proceedings Paper
Computer Science, Theory & Methods
Peng-Jun Wan, Fahad Al-Dhelaan, Xiaohua Jia, Baowei Wang, Guowen Xing
2015 IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (INFOCOM)
(2015)
Article
Computer Science, Theory & Methods
Sheng Wang, Shiping Chen, Fei Meng, Yumei Shi
Summary: This study proposes a Multi-Scenarios Adaptive Hierarchical Spatial Graph Convolution Network (MSHGN) model for accurately predicting GPU utilization rates in heterogeneous GPU clusters. By constructing multiple scenarios' undirected graphs and using Graph Convolution Neural (GCN) to capture spatial dependency relationships, the MSHGN model achieves superior accuracy and robustness in predicting resource utilization on a real-world Alibaba dataset.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Nik Amir Syafiq, Mohamed Othman, Norazak Senu, Fudziah Ismail, Nor Asilah Wati Abdul Hamid
Summary: This research investigates the multi-core architecture for solving the fractional Poisson equation using the modified accelerated overrelaxation (MAOR) scheme. The feasibility of the scheme in a parallel environment was tested through experimental comparisons and measurements. The results showed that the scheme is viable in a parallel environment.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Antonio F. Diaz, Beatriz Prieto, Juan Jose Escobar, Thomas Lampert
Summary: This paper presents the design and implementation of a low-cost energy monitoring system that synchronously collects the energy consumption of multiple devices using a specially designed wattmeter, and utilizes widely used technologies and tools in the Internet of Things for implementation.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Ritam Ganguly, Yingjie Xue, Aaron Jonckheere, Parker Ljung, Benjamin Schornstein, Borzoo Bonakdarpour, Maurice Herlihy
Summary: This paper presents a centralized runtime monitoring technique for distributed systems, which verifies the correctness of distributed computations by exploiting bounded-skew clock synchronization. By introducing a progression-based formula rewriting scheme and utilizing SMT solving techniques, the metric temporal logic can be monitored and the probabilistic guarantee for verification results can be calculated. Experimental results demonstrate the effectiveness of this technique in different application scenarios.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Arya Tanmay Gupta, Sandeep S. Kulkarni
Summary: Lattice-linear systems allow nodes to execute asynchronously. The eventually lattice-linear algorithms introduced in this study guarantee system transitions to optimal states within specified moves, leading to improved performance compared to existing literature. Experimental results further support the benefits of lattice-linearity.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Tim Breitenbach, Shrikanth Malavalli Divakar, Lauritz Rasbach, Patrick Jahnke
Summary: With the trend towards multi-socket server systems, the demand for RAM per server has increased, resulting in more DIMM sockets per server. RAM issues have become a dominant failure pattern for servers due to the probability of failure in each DIMM. This study introduces an ML-driven framework to estimate the probability of memory failure for each RAM module. The framework utilizes structural information between correctable (CE) and uncorrectable errors (UE) and engineering measures to mitigate the impact of UE.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Carlos Ansotegui, Eduard Torres
Summary: This paper presents an incomplete algorithm for efficiently constructing Covering Arrays with Constraints of high strength. The algorithm mitigates memory blow-ups and reduces run-time consumption, providing a practical tool for Combinatorial Testing.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Lucas Perotin, Sandhya Kandaswamy, Hongyang Sun, Padma Raghavan
Summary: Resource scheduling is crucial in High-Performance Computing systems, and previous research has mainly focused on a single type of resource. With advancements in hardware and the rise of data-intensive applications, considering multiple resources simultaneously is necessary to improve overall application performance. This study presents a Multi-Resource Scheduling Algorithm (MRSA) that minimizes the makespan of computational workflows by efficiently allocating resources and optimizing scheduling order. Simulation results demonstrate that MRSA outperforms baseline methods in various scenarios.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Yue Li, Han Liu, Jianbo Gao, Jiashuo Zhang, Zhi Guan, Zhong Chen
Summary: The processing of block lifecycles is crucial to the efficiency of a blockchain. The FASTBLOCK framework, which introduces fine-grained concurrency, accelerates the execution and validation steps. It outperforms state-of-the-art solutions significantly in terms of performance.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Roberto Carrasco, Hector Ferrada, Cristobal A. Navarro, Nancy Hitschfeld
Summary: The experimental evaluation of GPU filters for computing the 2D convex hull shows significant performance improvement. The different point distributions have a noticeable impact on the results, with the greatest improvement seen in the case of uniform and normal distributions.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Keqin Li
Summary: In this paper, the authors study task scheduling with or without energy constraint in mobile edge computing. They propose heuristic algorithms to solve these problems and analyze them using the methods of communication unification, effective speed concept, and virtual task construction. The experimental results show that the performance of the heuristic algorithms is close to the optimal algorithm. This is the first paper in the literature to optimize the makespan of task scheduling with or without energy constraint in mobile edge computing with multiple cloud-assisted edge servers.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Hongliang Li, Hairui Zhao, Ting Sun, Xiang Li, Haixiao Xu, Keqin Li
Summary: This paper studies the problem of job placement in shared GPU clusters and proposes an opportunistic memory sharing model and algorithms to solve the problem. Extensive experiments on a GPU cluster validate the correctness and effectiveness of the proposed approach.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Lucas Ruchel, Edson Tavares de Camargo, Luiz Antonio Rodrigues, Rogerio C. Turchetti, Luciana Arantes, Elias Procopio Duarte Jr.
Summary: LHABcast is a leaderless hierarchical atomic broadcast algorithm that improves scalability by being fully decentralized and hierarchical. It uses local sequence numbers and timestamps to order messages and achieves significantly lower message count compared to an all-to-all strategy, both in fault-free and faulty scenarios.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Xiangyu Wu, Xuehui Du, Qiantao Yang, Na Wang, Wenjuan Wang
Summary: This paper proposes a new method to address the immutability issue of consortium blockchains by introducing a verifiable distributed chameleon hash (VDCH) function and a consensus protocol called CVTSS based on verifiable threshold signatures. The proposed method enhances the flexibility, fault tolerance, and redaction efficiency of consortium blockchains.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
Article
Computer Science, Theory & Methods
Ipsita Behera, Srichandan Sobhanayak
Summary: Task scheduling in cloud computing is a challenging problem, and researchers propose a hybrid algorithm that aims to minimize makespan, energy consumption, and cost. Evaluation using the Cloudsim toolkit demonstrates the algorithm's effectiveness and efficiency.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2024)
