An efficient algorithm to solve connectivity problem on trapezoid graphs

DOI10.1007/BF02832306MaRDI QIDQ2454971zbMATHOpenAlexFDO

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

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)

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

Cites work

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

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)