A tight lower bound for Steiner orientation

DOI10.1007/978-3-319-90530-3_7zbMath1484.68155OpenAlexW2799833205MaRDI QIDQ1625142

Rajesh Chitnis, Andreas Emil Feldmann

Publication date: 28 November 2018

Full work available at URL: http://pure-oai.bham.ac.uk/ws/files/90694386/C20_A_Tight_Lower_Bound_for_Steiner.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ A tight lower bound for planar Steiner orientation

This page was built for publication: A tight lower bound for Steiner orientation