Approximating partially bounded degree deletion on directed graphs

DOI10.1007/978-3-319-75172-6_4zbMath1498.05113MaRDI QIDQ1641092

Toshihiro Fujito, Kei Kimura, Yuki Mizuno

Publication date: 15 June 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-75172-6_4

zbMATH Keywords

approximation algorithms; partial cover; bounded degree deletion

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C20: Directed graphs (digraphs), tournaments

05C07: Vertex degrees