An efficient algorithm to solve connectivity problem on trapezoid graphs

DOI10.1007/BF02832306zbMATH Open1124.68114OpenAlexW2093512944MaRDI QIDQ2454971FDOQ2454971

Authors: Prabir K. Ghosh, Madhumangal Pal 

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

Recommendations

• Efficient algorithm for the vertex connectivity of trapezoid graphs
• scientific article; zbMATH DE number 1696629
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• An efficient algorithm to solve the conditional covering problem on trapezoid graphs
• An efficient algorithm to find next-to-shortest path on trapezoid graphs
• Efficient algorithm for minimum feedback vertex set problem on trapezoid graphs
• An efficient algorithm for finding all hinge vertices on trapezoid graphs
• Efficient maximum matching algorithms for trapezoid graphs
• scientific article; zbMATH DE number 992410
• An optimal algorithm to solve 2-neighbourhood covering problem on trapezoid graphs

zbMATH Keywords

connected componentsvertex connectivitydesign and analysis of algorithmtrapezpoid graph

Mathematics Subject Classification ID

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

Cites Work

• Network Flow and Testing Graph Connectivity
• 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
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs

Cited In (2)

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

This page was built for publication: An efficient algorithm to solve connectivity problem on trapezoid graphs

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