In-place algorithms for computing a largest clique in geometric intersection graphs

DOI10.1016/j.dam.2014.06.025zbMath1300.05298OpenAlexW2524329448MaRDI QIDQ741534

Subhas C. Nandy, Sasanka Roy, Minati De

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.06.025

zbMATH Keywords

cliquebipartite matchinggeometric intersection graphsin-place algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space complexity of perfect matching in bounded genus bipartite graphs
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• On a circle placement problem
• Unit disk graphs
• Label placement by maximum independent set in rectangles
• Sphere of influence graphs: Edge density and clique size
• Sphere of influence graphs in general metric spaces
• A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
• Constant Depth Reducibility
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• An improved algorithm for the rectangle enclosure problem
• Simple heuristics for unit disk graphs
• Algorithms – ESA 2004

This page was built for publication: In-place algorithms for computing a largest clique in geometric intersection graphs