Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Parallelization of sequential algorithms
View through CrossRef
Abstract
In this chapter we show several implementations of sequential algorithms. Unfortunately in the case of parallel matchings such an approach does not usually give NC-algorithms for general graphs, though a reasonable parallel speed-up can be achieved. In some special cases (e.g. expander graphs, approximations) the implementation of sequential algorithms leads to NC-algorithms. We have already shown an application of maximal matchings to maximum matchings in the construction of an NC-algorithm for maximum matchings in dense graphs. In this chapter we show yet another application of NC-algorithms for maximal matchings: the sublinear time computation of maximum matchings in bipartite graphs. Denote by NC_Maxima_Match(G) an NC-function returning any maximal matching of a given graph G. Any of the algorithms presented in Chapter 7 can be used as a function NC_Maxima_Match(G) returning a maximal matching and working in polylogarithmic time with a linear number of processors. A parallel version of Hopcroft-Karp algorithm will be presented using NC_Maxima_Match as the main subroutine in the crucial operation Disjoint_Paths.
Oxford University PressOxford
Title: Parallelization of sequential algorithms
Description:
Abstract
In this chapter we show several implementations of sequential algorithms.
Unfortunately in the case of parallel matchings such an approach does not usually give NC-algorithms for general graphs, though a reasonable parallel speed-up can be achieved.
In some special cases (e.
g.
expander graphs, approximations) the implementation of sequential algorithms leads to NC-algorithms.
We have already shown an application of maximal matchings to maximum matchings in the construction of an NC-algorithm for maximum matchings in dense graphs.
In this chapter we show yet another application of NC-algorithms for maximal matchings: the sublinear time computation of maximum matchings in bipartite graphs.
Denote by NC_Maxima_Match(G) an NC-function returning any maximal matching of a given graph G.
Any of the algorithms presented in Chapter 7 can be used as a function NC_Maxima_Match(G) returning a maximal matching and working in polylogarithmic time with a linear number of processors.
A parallel version of Hopcroft-Karp algorithm will be presented using NC_Maxima_Match as the main subroutine in the crucial operation Disjoint_Paths.
Related Results
A Review of the Parallelization Strategies for Iterative Algorithms
A Review of the Parallelization Strategies for Iterative Algorithms
Abstract
Iteration-based algorithms have been widely used and achieved excellent results in many fields. However, in the big data era, data that needs to be processed is en...
Sequential Speciation and Cascading Divergence
Sequential Speciation and Cascading Divergence
A central, long-standing, and largely untested premise in evolutionary ecology is that “biodiversity begets biodiversity” in a process referred to as “sequential” or “cascading” di...
Classification with Single Constraint Progressive Mining of Sequential Patterns
Classification with Single Constraint Progressive Mining of Sequential Patterns
<span>Classification based on sequential pattern data has become an important topic to explore. One of research has been carried was the Classify-By-Sequence, CBS. CBS classi...
Comparative Analysis of Classical and Quantum Machine Learning Algorithms in Breast Cancer Classification
Comparative Analysis of Classical and Quantum Machine Learning Algorithms in Breast Cancer Classification
Abstract
This study presents a comparison between classical machine learning (ML) algorithms and their quantum-enhanced counterparts in classifying scikit’s breast ...
Mining spatiotemporal association rule based on prevalent sequential patterns
Mining spatiotemporal association rule based on prevalent sequential patterns
Abstract
Spatiotemporal association rules mining algorithms can effectively mine the association relationships between spatiotemporal event patterns, which plays an importa...
Asymptotical problems of sequential interval and point estimation
Asymptotical problems of sequential interval and point estimation
The accuracy of interval estimation systems is usually measured using interval lengths for given covering probabilities. The confidence intervals are the intervals of a fixed width...
On δ-Sequential Spaces
On δ-Sequential Spaces
Sequence converges is an important research object in topology and analysis, since it is closely related to continuity, compactness and other related properties. In this article, w...
Non-sequential response in Mountainous Area of Southwest China
Non-sequential response in Mountainous Area of Southwest China
<p>Non-sequential response, the phenomenon that the water storage change in the lower layer bigger than that of the adjacent upper layer within a set time interval, i...