Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 8/2017

30.01.2017

On the restricted connectivity of the arrangement graph

verfasst von: Eddie Cheng, Ke Qiu, Zhizhang Shen

Erschienen in: The Journal of Supercomputing | Ausgabe 8/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We derive a general upper bound of the \(R_h\) -restricted connectivity for the arrangement graph, namely the minimum cardinality of a vertex set, whose removal disconnects the graph, but every remaining vertex has at least \(h ({\ge }0)\) neighbors in the survival graph. We show that this upper bound is exact when \(h \in [0, 2]\) and provide an asymptotic lower bound for the cases where \(h\ge 3\).
Vorheriger Artikel HFIM: a Spark-based hybrid frequent itemset mining algorithm for big data processing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Based on the assumption that all the vertex cut sets consisting of all the neighbors of some vertex should be forbidden, every vertex in the survival graph, by the definition made in [27], has at least \(h+1\) neighbors, \(h\ge 0\). Following the lead of other works [28, 34, 35, 38], we allow the possibility that such a vertex has no neighbor in the survival graph; thus, vertex connectivity becomes a special case of the \(R_h\)-vertex connectivity.
 
2
For example, in Fig. 1, if we take X be \(\{12, 14\},\) then \(S=\{13, 24, 32, 34, 42\}.\) Clearly, \(G_X\) is isomorphic to \(K_2,\) i.e., an edge.
 
3
For example, in Fig. 1, 12 and 14 of \(K_2^1\) are adjacent to 32 and 34 of \(K_2^3,\) respectively.
 
4
This is the case that calls for \(h < n-k.\)
 
Literatur
1.
Akers SB, Krishnamurthy B (1989) A group theoretic model for symmetric interconnection networks. IEEE Trans Comput 38(4):555–566MathSciNetCrossRefMATH
2.
3.
Arabnia HR (1995) A distributed stereocorrelation algorithm. In: Proceedings of Computer Communications and Networks (ICCCN’95). IEEE, pp 479–482
4.
Arabnia HR, Smith JW (1993) A reconfigurable interconnection network for imaging operations and its implementation using a multi-stage switching box. In: Proceedings of the 7th Annual International High Performance Computing Conference, the 1993 High Performance Computing: New Horizons Supercomputing Symposium. Calgary, pp 349–357
5.
Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput 10(2):188–193CrossRef
6.
Arabnia HR, Bhandarkar SM (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput 10(3):243–270CrossRefMATH
7.
Arabnia HR, Oliver MA (1986) Fast operations on raster images with SIMD machine architectures. Int J Eurograph Assoc Comput Graph Forum 5(3):179–188CrossRef
8.
Arabnia HR, Oliver MA (1987) Arbitrary rotation of raster images with SIMD machine architectures. Int J Eurograph Assoc Comput Graph Forum 6(1):3–12CrossRef
9.
Arabnia HR, Oliver MA (1987) A transputer network for the arbitrary rotation of digitised images. Comput J 30(5):425–433CrossRef
10.
Arabnia HR, Oliver MA (1989) A transputer network for fast operations on digitised images. Int J Eurograph Assoc Comput Graph Forum 8(1):3–12CrossRef
11.
Bhandarkar SM, Arabnia HR, Smith JW (1995) A reconfigurable architecture for image processing and computer vision. Int J Pattern Recognit Artif Intell (IJPRAI) 9(2):201–229CrossRef
12.
Bhandarkar SM, Arabnia HR (1995) The Hough transform on a reconfigurable multi-ring network. J Parallel Distrib Comput 24(1):107–114CrossRef
13.
Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor: theoretical properties and algorithms. Parallel Comput 21(11):1783–1806CrossRef
14.
Cheng E, Lipták L, Sala F (2010) Linearly many faults in 2-tree generated networks. Networks 55:90–98MathSciNetMATH
15.
16.
Cheng E, Lipman MJ (2001) Super connectivity of star graphs, alternating group graphs and split-stars. Ars Comb 59:107–116MathSciNetMATH
17.
Cheng E, Lipták L, Qiu K, Shen Z (2013) A unified approach to the conditional diagnosability of interconnection networks. J Interconnect Netw 13(3–4):1250007
18.
19.
20.
Denning PJ, Lewis TG (2017) Exponential laws of computing growth. Commun ACM 60(1):54–65CrossRef
21.
Esfahanian AH (1989) Generalized measure of fault tolerance with application to \(N\)-cube networks. IEEE Trans Comput 38:1586–1591CrossRef
22.
Gu M-M, Hao R-X, Yang DX (2016) A short note on the 1,2-good-neighbor diagnosability of balanced hypercubes. J Interconnect Netw 16(1&2):1650001CrossRef
23.
24.
Hsieh S-Y, Chen G-H, Ho C-W (1999) Fault-free Hamiltonian cycles in faulty arrangement graphs. IEEE Trans Parallel Distrib Syst 10(3):223–237CrossRef
25.
26.
Lai P-L, Tan J-J, Chang C-P, Hsu L-H (2005) Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Comput 54(2):165–175CrossRef
27.
Latifi S, Hegde M, Pour MN (1994) Conditional connectivity measures for large multiprocessor systems. IEEE Trans Comput 43:218–222CrossRef
28.
Li XJ, Xu J-M (2014) Faulty-tolerance of \((n, k)\)-star networks. Appl Math Comput 248:525–530MathSciNetMATH
29.
Oh AD, Choi H (1993) Generalized measures of fault tolerance in \(n\)-cube networks. IEEE Trans Parallel Distrib Syst 4:702–703CrossRef
30.
Peng S-L, Lin C-K, Tan J-J, Hsu L-H (2012) The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model. Appl Math Comput 218(21):10406–10412MathSciNetMATH
31.
32.
33.
Wani MA, Arabnia HR (2003) Parallel edge-region-based segmentation algorithm targeted at reconfigurable multi-ring network. J Supercomput 25(1):43–63CrossRefMATH
34.
35.
Yang W, Li H, Guo X (2010) A kind of conditional fault tolerance of \((n, k)\)-star graphs. Inform Process Lett 110:1007–1011MathSciNetCrossRef
36.
Yuan J, Liu A, Ma X, Liu X, Qin X, Zhang J (2015) The \(g\)-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model. IEEE Trans Parallel Distrib Syst 26:1165–1177CrossRef
37.
Zhang Z, Xiong W, Yang WH (2010) A kind of conditional fault tolerance alternating group graphs. Inform Process Lett 110:998–1002MathSciNetCrossRef
38.
Metadaten
Titel
On the restricted connectivity of the arrangement graph
verfasst von
Eddie Cheng
Ke Qiu
Zhizhang Shen
Publikationsdatum
30.01.2017
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 8/2017
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-017-1964-3

Weitere Artikel der Ausgabe 8/2017

The Journal of Supercomputing 8/2017 Zur Ausgabe

OriginalPaper

Cache-conscious run-time decomposition of data parallel computations

OriginalPaper

SLA-aware energy-efficient scheduling scheme for Hadoop YARN

OriginalPaper

Supporting high-quality video streaming with SDN-based CDNs

OriginalPaper

Shared write buffer to boost applications on SpMT architecture

OriginalPaper

KTS: a real-time mapping algorithm for NoC-based many-cores

OriginalPaper

Efficient implementation of Jacobi iterative method for large sparse linear systems on graphic processing units