On the Strongly Connected and Biconnected Components of the Complement of Graphs

DOI10.1016/J.ENDM.2004.03.044MaRDI QIDQ3439158zbMATH OpenOpenAlexFDO

Authors Stavros D. Nikolopoulos, Leonidas Palios

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2004.03.044

Mathematics Subject Classification ID

Connectivity (05C40)

Recommendations

• The connectivity of a bipartite graph and its bipartite complementary graph
• The connectivity of a graph and its complement
• scientific article; zbMATH DE number 7132839
• The g-component connectivity of graphs
• Connected complementary graphs relative to \(K_{a,b}\) and some Nordhaus-Gaddum type results
• A note on the algebraic connectivity of a graph and its complement
• scientific article; zbMATH DE number 637619
• The algebraic connectivity of a graph and its complement
• On complementary decompositions of the complete graph
• On the complements of graphs

Cites work

• An O(logn) parallel connectivity algorithm
• An optimal parallel co-connectivity algorithm
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Computing connected components on parallel computers
• Efficient parallel algorithms for some graph problems
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3576688 (Why is no real title available?)
• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• Improving the efficiency of parallel minimum spanning tree algorithms
• Introduction to algorithms
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Parallel algorithms for the connected components and minimal spanning tree problems

Cited in

(9)

• Finding biconnected components in O(n) time for a class of graphs
• Why should biconnected components be identified first
• A simplified correctness proof for a well-known algorithm computing strongly connected components.
• An optimal parallel co-connectivity algorithm
• Strength and fractional arboricity of complementary graphs
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Twinless strongly connected components
• RECOGNITION OF STRONGLY CONNECTED COMPONENTS BY THE LOCATION OF NONZERO ELEMENTS OCCURRING IN C(G) = (D - A(G))^-1

This page was built for publication: On the Strongly Connected and Biconnected Components of the Complement of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3439158)