Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
From MaRDI portal
Publication:6174144
DOI10.1142/s179383092250063xMaRDI QIDQ6174144
Sharareh Alipour, Salman Parsa
Publication date: 14 July 2023
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
68Rxx: Discrete mathematics in relation to computer science
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplified NP-complete satisfiability problem
- Visibility and intersection problems in plane geometry
- The complexity of planar compliant motion planning under uncertainty
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Optimization, approximation, and complexity classes
- An efficient algorithm for one-step planar compliant motion planning with uncertainty
- A special planar satisfiability problem and a consequence of its NP- completeness
- Finding the shortest watchman route in a simple polygon
- An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
- Connectivity graphs of uncertainty regions
- Visibility testing and counting for uncertain segments
- Improved Approximation Algorithms for MAX SAT
- Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements
- Planar Formulae and Their Uses
- The Complexity of Multiterminal Cuts
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Region-based Approximation Algorithms for Visibility between Imprecise Locations
- Computing the visibility graph of points within a polygon
- The complexity of satisfiability problems
- Planar visibility
- Some optimal inapproximability results
- Visibility Algorithms in the Plane
- Approximating Watchman Routes
- Hard tiling problems with simple tiles
