File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Algorithms for Placing Monitors in a Flow Network

TitleAlgorithms for Placing Monitors in a Flow Network
Authors
Issue Date2009
PublisherSpringer Berlin Heidelberg.
Citation
The 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009), San Francisco, CA, 15-17 June 2009. In Algorithmic Aspects in Information and Management, 2009, v. 5564, p. 114-128 How to Cite?
AbstractIn the Flow Edge-Monitor Problem, we are given an undirected graph G = (V,E), an integer k > 0 and some unknown circulation ψ on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem is NP-hard, and then we give two approximation algorithms: a 3-approximation algorithm with running time O((m + n)2) and a 2-approximation algorithm with running time O((m + n)3), where n = |V| and m = |E|.
Persistent Identifierhttp://hdl.handle.net/10722/61201
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
Series/Report no.Lecture Notes in Computer Science

 

DC FieldValueLanguage
dc.contributor.authorChin, FYL-
dc.contributor.authorChrobak, M-
dc.contributor.authorYan, L-
dc.date.accessioned2010-07-13T03:33:03Z-
dc.date.available2010-07-13T03:33:03Z-
dc.date.issued2009-
dc.identifier.citationThe 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009), San Francisco, CA, 15-17 June 2009. In Algorithmic Aspects in Information and Management, 2009, v. 5564, p. 114-128-
dc.identifier.isbn9783642021572-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/61201-
dc.description.abstractIn the Flow Edge-Monitor Problem, we are given an undirected graph G = (V,E), an integer k > 0 and some unknown circulation ψ on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem is NP-hard, and then we give two approximation algorithms: a 3-approximation algorithm with running time O((m + n)2) and a 2-approximation algorithm with running time O((m + n)3), where n = |V| and m = |E|.-
dc.languageeng-
dc.publisherSpringer Berlin Heidelberg.-
dc.relation.ispartofAlgorithmic Aspects in Information and Management-
dc.relation.ispartofseriesLecture Notes in Computer Science-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/[insert DOI]-
dc.titleAlgorithms for Placing Monitors in a Flow Network-
dc.typeConference_Paper-
dc.identifier.emailChin, FYL: chin@cs.hku.hk-
dc.identifier.authorityChin, FYL=rp00105-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-02158-9_11-
dc.identifier.scopuseid_2-s2.0-70350641432-
dc.identifier.hkuros166447-
dc.identifier.volume5564-
dc.identifier.spage114-
dc.identifier.epage128-
dc.publisher.placeSan Francisco, CA-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats