An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs

DOI10.1080/00207160212707MaRDI QIDQ3147308zbMATH OpenOpenAlexFDO

Authors Debashis Bera, Madhumangal Pal, Tapan K. Pal

Publication date 11 December 2002

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160212707

zbMATH Keywords

algorithmmaximal cliquetrapezoid graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

Trapezoid graphs are the incomparability graphs of partial orders with interval dimension at most two. A clumsy algorithm lists the maximal cliques of a trapezoid graph on \(n\) vertices in time \(O(n^2+\gamma n)\) where \(\gamma\) is the size of the output.

Recommendations

• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and generalizations, geometry and algorithms
• Efficient maximum matching algorithms for trapezoid graphs
• Trapezoid graphs and their coloring

Cites work

• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Fast Parallel Algorithms for Chordal Graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4072403 (Why is no real title available?)
• On the 2-Chain Subgraph Cover and Related Problems
• On the structure of trapezoid graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Trapezoid graphs and their coloring

Cited in

(9)

• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• An efficient algorithm to solve connectivity problem on trapezoid graphs
• Max-min weight balanced connected partition
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Efficient maximum matching algorithms for trapezoid graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• Counting the number of vertex covers in a trapezoid graph

This page was built for publication: An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs

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