Efficient algorithm for the vertex connectivity of trapezoid graphs
From MaRDI portal
Publication:396607
DOI10.1016/j.ipl.2013.02.012zbMath1358.05280arXiv1106.3037OpenAlexW2963005395MaRDI QIDQ396607
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
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Efficient maximum matching algorithms for trapezoid graphs ⋮ On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines
Cites Work
- Unnamed Item
- Unnamed Item
- Trapezoid graphs and generalizations, geometry and algorithms
- Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time
- Efficient algorithms for the minimum connected domination on trapezoid graphs
- Counting the number of vertex covers in a trapezoid graph
- Trapezoid graphs and their coloring
- Dominations in 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
- On the structure of trapezoid graphs
- An efficient algorithm to solve connectivity problem on trapezoid graphs
- Chaining algorithms for multiple genome comparison
- A generalization of the Euler beta function and applications
- An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
- Network Flow and Testing Graph Connectivity
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- On the 2-Chain Subgraph Cover and Related Problems
- Extremal interval graphs
- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
