Title:

On Increasing Parallelism in the Forward-Backward Distributed Algorithm forFinding Strongly Connected Components of Directed Graphs, Journal of Telecommunications and Information Technology, 2024, nr 3

Group publication title:

2024, nr 3, JTIT-artykuły

Creator:

Ryżko, Dominik

Subject and Keywords:

distributed computations ; graph algorithms ; strongly connected components

Abstrakt:

The paper proposes a modification of the existing distributed forward-backward algorithm for finding strongly connected components in directed graphs. The modification aims at improving the parallelism of the algorithm by increasing the branching factor while dividing the workload. Instead of randomly picking the pivot vertex, a heuristic technique is used which allows more sub-tasks to be generated, on average, for the subsequent step of the algorithm. The work describes suitable algorithm modifications and presents empirical results, proving suitability of the approach in question.

Number:

3

Publisher:

National Institute of Telecommunications

Date:

2024, nr 3

Resource Type:

artykuł

Resource Identifier:

ISSN 1509-4553, on-line: ISSN 1899-8852

DOI:

10.26636/jtit.2024.3.1693

ISSN:

1509-4553

eISSN:

1899-8852

Source:

Journal of Telecommunications and Information Technology

Language:

ang

License:

CC BY 4.0

rights owner:

Instytut Łączności - Państwowy Instytut Badawczy