scientific article; zbMATH DE number 6707504

DOI10.20382/JOCG.V8I2A5MaRDI QIDQ2978407zbMATH OpenFDO

Authors Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals

Publication date 24 April 2017

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

zbMATH Keywords

complexity boundscomputer graphicsminimum-link path problempolynomial-time approximation scheme

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the complexity of minimum-link path problems
• Minimum-link paths revisited
• On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms
• The complexity of minimum-length path decompositions
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• Solving min-max shortest-path problems on a network
• On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
• On the difficulty of some shortest path problems
• scientific article; zbMATH DE number 1962826

Cited in

(14)

• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• The complexity of drawing a graph in a polygonal region
• Embedding ray intersection graphs and global curve simplification
• Minimum-link paths revisited
• On the complexity of minimum-link path problems
• The Minimum Reload s-t Path/Trail/Walk Problems
• The complexity of drawing a graph in a polygonal region
• Smoothing the Gap Between NP and ER
• Global Curve Simplification
• Link-Length Minimization in Networks
• Global optimization: On pathlengths in min-max graphs
• Link diameter, radius and 2-point link distance queries in polygonal domains
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• The minimum reload \(s-t\) path, trail and walk problems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978407)