On Local Search and Placement of Meters in Networks
From MaRDI portal
Publication:4706214
DOI10.1137/S0097539799363359zbMath1033.90107MaRDI QIDQ4706214
Samir Khuller, Robert Pless, Randeep Bhatia
Publication date: 19 June 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
90C27: Combinatorial optimization
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem, Local search: is brute-force avoidable?, On the directed full degree spanning tree problem, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Two feedback problems for graphs with bounded tree-width, Parameterized complexity and local search approaches for the stable marriage problem with ties, On the parameterized complexity of consensus clustering, On the complexity of restoring corrupted colorings, Sharp separation and applications to exact and parameterized algorithms, Algorithms for placing monitors in a flow network, Searching for better fill-in, Fixed-parameter tractability results for full-degree spanning tree and its dual, The degree-preserving spanning tree problem in strongly chordal and directed path graphs, A Moderately Exponential Time Algorithm for Full Degree Spanning Tree, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT, Algorithms for Placing Monitors in a Flow Network, On the Directed Degree-Preserving Spanning Tree Problem