Terminal Backup, 3D Matching, and Covering Cubic Graphs

DOI10.1137/090752699zbMath1229.05224OpenAlexW1988936512MaRDI QIDQ3093619

Adriana Karagiozova, Elliot Anshelevich

Publication date: 18 October 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090752699

zbMATH Keywords

network designgraph packingcycle coversimplex matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (11)

Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity ⋮ The Generalized Terminal Backup Problem ⋮ Optimal general factor problem and jump system intersection ⋮ Strategic cooperation in cost sharing games ⋮ Resource buying games ⋮ Pattern-guided \(k\)-anonymity ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ Clustering with lower-bounded sizes. A general graph-theoretic framework ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation

This page was built for publication: Terminal Backup, 3D Matching, and Covering Cubic Graphs