One-sided terrain guarding and chordal graphs

DOI10.1016/J.DAM.2024.01.034OpenAlexW4391553434WikidataQ128662081 ScholiaQ128662081MaRDI QIDQ6204302

Prahlad Narasimhan Kasthurirangan

Publication date: 27 March 2024

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

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

zbMATH Keywords

chordal graphsterrain guardingvisibility graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved approximations for guarding 1.5-dimensional terrains
• One-sided discrete terrain guarding and chordal graphs
• Improved approximation algorithms for geometric set cover
• Characterizations of strongly chordal graphs
• An optimal visibility graph algorithm for triangulated simple polygons
• Parameter analysis for guarding terrains
• A fixed-parameter algorithm for guarding 1.5D terrains
• On guarding the vertices of rectilinear domains
• Guarding terrains via local search
• On characterizing terrain visibility graphs
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• Exact Algorithms for Terrain Guarding
• Unsolved problems in visibility graphs of points, segments, and polygons
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Visibility Algorithms in the Plane
• Parameterized Algorithms
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains

This page was built for publication: One-sided terrain guarding and chordal graphs