Many-to-many disjoint paths in hypercubes with faulty vertices
| Autor: | Xiang-Jun Li, Bin Liu, Meijie Ma, Jun-Ming Xu |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Applied Mathematics 0102 computer and information sciences 02 engineering and technology Disjoint sets 01 natural sciences Vertex (geometry) Linear algorithm Combinatorics Integer 010201 computation theory & mathematics FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Mathematics - Combinatorics Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Combinatorics (math.CO) Hypercube Many-to-many (data model) Mathematics |
| Zdroj: | Discrete Applied Mathematics. 217:229-242 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2016.09.013 |
| Popis: | This paper considers the problem of many-to-many disjoint paths in the hypercube Q n with f faulty vertices and obtains the following result. For any integer k with 1 ź k ź n - 1 and any two sets S and T of k fault-free vertices in different partite sets of Q n ( n ź 2 ) , if f ź 2 n - 2 k - 2 and each fault-free vertex has at least two fault-free neighbors, then there exist k fully disjoint fault-free paths linking S and T which contain at least 2 n - 2 f vertices. A linear algorithm for finding such disjoint paths is also given. This result improves some known results in a sense. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect