Redundancy elimination in the estimation of multiple paths

MaRDI QIDQ2722583zbMATH OpenFDO

Authors Stefano Casadei

Publication date 2 December 2002

zbMATH Keywords

approximation in graphs by pathsdistance measuresgraphimage reconstructionmetric on paths

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computing methodologies for image processing (68U10) Estimation and detection in stochastic control theory (93E10)

Review text

This paper considers approximating certain objects by source-to-sink graphs in a directed acyclic graph. Three distance measures are assumed to exist, a metric on the paths, an estimated distance from vertices to their closest objects, and a distance from vertices to specified objects. The latter two distance measures seem unrelated; both are extended to paths by taking maxima. The author defines a certain subset \(S\) of all objects, and proves the following. If an object of \(S\) can be closely approximated by a path then it can be approximated by a path out of a set of well-separated paths in the graph. However, it remains open under what conditions the object set \(S\) is non-empty, or contains a meaningful portion of all objects given. For the entire collection see [Zbl 0961.00036].

Recommendations

• Counting approximately-shortest paths in directed acyclic graphs
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximately counting approximately-shortest paths in directed acyclic graphs
• scientific article; zbMATH DE number 1875406
• A note on approximating the min-max vertex disjoint paths on directed acyclic graphs

Cited in

(2)

• scientific article; zbMATH DE number 3913516 (Why is no real title available?)
• Multi-path vs. single-path replies to skepticism

This page was built for publication: Redundancy elimination in the estimation of multiple paths

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