Perfect Graphs and Orthogonally Convex Covers

DOI10.1137/0402033zbMath0674.05070OpenAlexW2066239131MaRDI QIDQ3828050

Huzur Saran, Arvind U. Raghunathan, Rajeev Motwani

Publication date: 1989

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0402033

zbMATH Keywords

visibility graphpermutation graphorthogonal polygonsweakly triangulated graphsminimal coverings

Mathematics Subject Classification ID

Graph theory (05C99) Polytopes and polyhedra (52Bxx)

Related Items (17)

Covering grids and orthogonal polygons with periscope guards ⋮ Algorithms for weakly triangulated graphs ⋮ Staircase visibility and computation of kernels ⋮ Note on covering monotone orthogonal polygons with star-shaped polygons ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ A hybrid heuristic for the rectilinear picture compression problem ⋮ A scheme for computing minimum covers within simple regions ⋮ Covering orthogonal polygons with star polygons: The perfect graph approach ⋮ Rectangle blanket problem: binary integer linear programming formulation and solution algorithms ⋮ Efficient algorithms for shortest distance queries on special classes of polygons ⋮ Complexities of efficient solutions of rectilinear polygon cover problems ⋮ LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM ⋮ POINT VISIBILITY GRAPHS AND ${\mathcal O}$-CONVEX COVER ⋮ Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem ⋮ An efficient algorithm for finding a two-pair, and its applications ⋮ Polyominos and perfect graphs

This page was built for publication: Perfect Graphs and Orthogonally Convex Covers