Efficient algorithm for the vertex connectivity of trapezoid graphs

DOI10.1016/J.IPL.2013.02.012MaRDI QIDQ396607zbMATHOpenAlexFDO

Authors Aleksandar Ilić

Publication date 13 August 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.3037

zbMATH Keywords

algorithmstrapezoid graphsvertex connectivitybinary indexed tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Connectivity (05C40)

Abstract: The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. These graphs and their generalizations were applied in various fields, including modeling channel routing problems in VLSI design and identifying the optimal chain of non-overlapping fragments in bioinformatics. Using modified binary indexed tree data structure, we design an algorithm for calculating the vertex connectivity of trapezoid graph $G$ with time complexity $O(nlogn)$, where $n$ is the number of trapezoids. Furthermore, we establish sufficient and necessary condition for a trapezoid graph $G$ to be bipartite and characterize trees that can be represented as trapezoid graphs.

Recommendations

• An efficient algorithm to solve connectivity problem on trapezoid graphs
• scientific article; zbMATH DE number 1696629
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• Efficient maximum matching algorithms for trapezoid graphs
• An efficient algorithm for finding all hinge vertices on trapezoid graphs
• Efficient algorithm for minimum feedback vertex set problem on trapezoid graphs
• An efficient algorithm to find next-to-shortest path on trapezoid graphs
• An efficient algorithm to solve the conditional covering problem on trapezoid graphs
• scientific article; zbMATH DE number 5313630
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

Cites work

• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• A generalization of the Euler beta function and applications
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
• An efficient algorithm for finding all hinge vertices on trapezoid graphs
• An efficient algorithm to solve connectivity problem on trapezoid graphs
• Chaining algorithms for multiple genome comparison
• Counting the number of vertex covers in a trapezoid graph
• Dominations in trapezoid graphs
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• Extremal interval graphs
• Introduction to algorithms
• Network Flow and Testing Graph Connectivity
• On the 2-Chain Subgraph Cover and Related Problems
• On the structure of trapezoid graphs
• Optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time

Cited in

(7)

• On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines
• Counting the number of vertex covers in a trapezoid graph
• Vertex splitting and the recognition of trapezoid graphs
• An efficient algorithm to solve connectivity problem on trapezoid graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• scientific article; zbMATH DE number 2159654 (Why is no real title available?)
• Efficient maximum matching algorithms for trapezoid graphs

This page was built for publication: Efficient algorithm for the vertex connectivity of trapezoid graphs

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