On Local Search and Placement of Meters in Networks

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)

zbMATH Keywords

local searchfeedback setsapproximation algorithmspressure-meters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem ⋮ A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ On the complexity of restoring corrupted colorings ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Local search: is brute-force avoidable? ⋮ Algorithms for placing monitors in a flow network ⋮ Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ On the directed full degree spanning tree problem ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Searching for better fill-in ⋮ Two feedback problems for graphs with bounded tree-width ⋮ On the parameterized complexity of consensus clustering ⋮ 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 ⋮ 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

This page was built for publication: On Local Search and Placement of Meters in Networks