Efficient algorithm for the vertex connectivity of trapezoid graphs

DOI10.1016/J.IPL.2013.02.012zbMATH Open1358.05280arXiv1106.3037OpenAlexW2963005395MaRDI QIDQ396607FDOQ396607

Aleksandar Ilić

Publication date: 13 August 2014

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

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.

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

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
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

zbMATH Keywords

algorithmstrapezoid graphsvertex connectivitybinary indexed tree

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• An efficient algorithm to solve connectivity problem on trapezoid graphs
• Title not available (Why is that?)
• On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines
• Vertex splitting and the recognition of trapezoid graphs
• 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)