Covering and packing of triangles intersecting a straight line

DOI10.1016/j.dam.2021.11.017zbMath1496.90080OpenAlexW4225738401MaRDI QIDQ5918763

Supantha Pandit

Publication date: 4 August 2022

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

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

zbMATH Keywords

dynamic programmingindependent setset coverhitting sethorizontal lineinclined linepiercing setright trianglesdiagonal line\( \mathsf{NP} \)-hard

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39)

Cites Work

• Unnamed Item
• Max point-tolerance graphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Approximation algorithms for maximum independent set of a unit disk graph
• The within-strip discrete unit disk cover problem
• A weighted min-max relation for intervals
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Clique partitioning of interval graphs with submodular costs on the cliques
• Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Covering and packing of triangles intersecting a straight line

This page was built for publication: Covering and packing of triangles intersecting a straight line