• Paired 2-disjoint path cover o...

Treffer: Paired 2-disjoint path cover of burnt pancake graphs with [formula omitted] faulty elements.

Title:
Paired 2-disjoint path cover of burnt pancake graphs with [formula omitted] faulty elements.
Authors:
Chen, Congzhen1,2 (AUTHOR), Li, Pingshan3,4 (AUTHOR) lips@xtu.edu.cn, Liu, Xianglin1,5 (AUTHOR) yx331229641@163.com
Source:
Discrete Applied Mathematics. Feb2026, Vol. 380, p307-325. 19p.
Subject Terms:
*GRAPH theory, *PARALLEL processing, *MATHEMATICAL optimization, *PERIODICAL articles
Database:
Academic Search Index

Weitere Informationen

Identifying k -vertex-disjoint paths that cover all vertices in the underlying graph of an interconnected network is a key challenge in parallel processing. This problem is classified as the paired or the unpaired k -disjoint path cover problem. In 2024, Dvořák and Gu (Theoretical Computer Science, 986 (2024) 114327) showed that there exist two disjoint paths forming a partition of the fault-free vertices of the burnt pancake graph even if the graph contains at most n − 4 faulty elements (vertices or edges) and they proposed an open problem: is it possible to improve the upper bound n − 4 to n − 3 ? In this paper, we provide a positive answer to this problem. [ABSTRACT FROM AUTHOR]