Publication:5891382

DOI10.1137/120883931zbMath1283.05257arXiv1112.2273OpenAlexW2069519792MaRDI QIDQ5891382

Marek Cygan, Zeev Nutov, Guy Kortsarz

Publication date: 21 January 2014

Published in: SIAM Journal on Discrete Mathematics, Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.2273

zbMATH Keywords

graph algorithmsapproximation algorithmsgraph orientationparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

On the fixed-parameter tractability of the maximum connectivity improvement problem, Approximating Minimum Cost Connectivity Orientation and Augmentation, Path-driven orientation of mixed graphs, A tight lower bound for planar Steiner orientation, Parameterized certificate dispersal and its variants