An efficient algorithm to solve connectivity problem on trapezoid graphs

DOI10.1007/BF02832306zbMath1124.68114OpenAlexW2093512944MaRDI QIDQ2454971

Madhumangal Pal, Prabir K. Ghosh

Publication date: 22 October 2007

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02832306

zbMATH Keywords

connected componentsvertex connectivitydesign and analysis of algorithmtrapezpoid graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Max-min weight balanced connected partition ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs

Cites Work

• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Network Flow and Testing Graph Connectivity