Please use this identifier to cite or link to this item:

`http://hdl.handle.net/2381/31666`

Title: | Minimum Spanning Tree Verification under Uncertainty |

Authors: | Erlebach, Thomas R. Hoffmann, Michael |

First Published: | 2014 |

Presented at: | 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014), Le Domaine de Chalès |

Start Date: | 25-Jun-2014 |

End Date: | 27-Jun-2014 |

Publisher: | Springer |

Citation: | Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014) |

Abstract: | In the verification under uncertainty setting, an algorithm is given, for each input item, an uncertainty area that is guaranteed to contain the exact input value, as well as an assumed input value. An update of an input item reveals its exact value. If the exact value is equal to the assumed value, we say that the update verifies the assumed value. We consider verification under uncertainty for the minimum spanning tree (MST) problem for undirected weighted graphs, where each edge is associated with an uncertainty area and an assumed edge weight. The objective of an algorithm is to compute the smallest set of updates with the property that, if the updates of all edges in the set verify their assumed weights, the edge set of an MST can be computed. We give a polynomial-time optimal algorithm for the MST verification problem by relating the choices of updates to vertex covers in a bipartite auxiliary graph. Furthermore, we consider an alternative uncertainty setting where the vertices are embedded in the plane, the weight of an edge is the Euclidean distance between the endpoints of the edge, and the uncertainty is about the location of the vertices. An update of a vertex yields the exact location of that vertex. We prove that the MST verification problem in this vertex uncertainty setting is NP-hard. This shows a surprising difference in complexity between the edge and vertex uncertainty settings of the MST verification problem. |

Series/Report no.: | Lecture Notes in Computer Science;8747 |

DOI Link: | 10.1007/978-3-319-12340-0_14 |

ISSN: | 0302-9743 |

ISBN: | 978-3-319-12340-0 |

Links: | http://www.springer.com/computer/theoretical+computer+science/book/978-3-319-12339-4 http://hdl.handle.net/2381/31666 http://link.springer.com/chapter/10.1007%2F978-3-319-12340-0_14 |

Version: | Post-print |

Status: | Peer-reviewed |

Type: | Conference Paper |

Rights: | Copyright © 2014, Springer. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website. |

Appears in Collections: | Conference Papers & Presentations, Dept. of Computer Science |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

WG2014finalauthorversion.pdf | Post-review (final submitted) | 152.97 kB | Adobe PDF | View/Open |

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.