46
Views
5
CrossRef citations to date
0
Altmetric
Original Articles

An algorithm for finding all the k-components of a digraph

Pages 213-221 | Received 01 Nov 1986, Published online: 19 Mar 2007
 

Abstract

A k-component of a digraph is a maximal subgraph in which k disjoint paths exist between every ordered pair of vertices. A digraph may have many k-components, namely 1-components, 2-components,..., and so on. This paper presents an algorithm to find all the possible k-components of a digraph with n vertices and e edges within 0(n max (n+ e,T)time for every k, where T denotes the time bound to find a minimum vertex separator of the digraph. This result is also available for a graph.

C.R. Categories:

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.