Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
From MaRDI portal
Publication:5479368
DOI10.1007/11538462zbMath1142.68460OpenAlexW2649657569MaRDI QIDQ5479368
Publication date: 7 July 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11538462
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items
Online maximum matching with recourse ⋮ Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ On Randomized Algorithms for Matching in the Online Preemptive Model ⋮ Maximum Matching in Turnstile Streams ⋮ Superlinear lower bounds for multipass graph processing ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Unnamed Item ⋮ Weighted matching in the semi-streaming model ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Bipartite matching in the semi-streaming model ⋮ Improved bounds for randomized preemptive online matching ⋮ Unnamed Item ⋮ Round Compression for Parallel Matching Algorithms ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Online Maximum Matching with Recourse ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Buyback Problem - Approximate Matroid Intersection with Cancellation Costs ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Structural results on matching estimation with applications to streaming ⋮ Streaming algorithm for graph spanners-single pass and constant processing time per edge ⋮ Evolutionary Network Analysis ⋮ Dynamic Approximate Vertex Cover and Maximum Matching ⋮ Unnamed Item ⋮ Semi-streaming algorithms for submodular matroid intersection ⋮ Semi-streaming algorithms for submodular matroid intersection ⋮ Depth First Search in the Semi-streaming Model ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Maximum matching on trees in the online preemptive and the incremental graph models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An estimator for matching size in low arboricity graphs with two applications
