Minimum Scan Cover with Angular Transition Costs

DOI10.1137/20M1368161zbMath1467.05045arXiv2003.08816OpenAlexW3174468750MaRDI QIDQ4997133

Linda Kleist, Dominik Krupke, Sándor P. Fekete

Publication date: 28 June 2021

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

Full work available at URL: https://arxiv.org/abs/2003.08816

zbMATH Keywords

schedulingapproximationgraph coloringangular metricgraph scanning

Mathematics Subject Classification ID

Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Metric geometry (51F99) Coloring of graphs and hypergraphs (05C15) Combinatorial complexity of geometric structures (52C45)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The third comprehensive survey on scheduling problems with setup times/costs
• Bounded-angle spanning tree: modeling networks with angular constraints
• Connectivity guarantees for wireless networks with directional antennas
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Forests, frames, and games: Algorithms for matroid sums and applications
• Minimal cut cover of a graph with an application to the testing of electronic boards
• Covering tours and cycle covers with turn costs: hardness and approximation
• A survey of scheduling problems with setup times or costs
• Angle-restricted tours in the plane.
• The minimum cut cover problem
• Hardness of cut problems in directed graphs
• Milling a Graph with Turn Costs: A Parameterized Complexity Perspective
• A Remark on Stirling's Formula
• The Angular-Metric Traveling Salesman Problem
• An improved approximation algorithm for TSP in the half integral case
• Practical Methods for Computing Large Covering Tours and Cycle Covers with Turn Cost
• A 1.5-Approximation for Path TSP
• Optimal Covering Tours with Turn Costs