A tight lower bound for Steiner orientation

DOI10.1007/978-3-319-90530-3_7MaRDI QIDQ1625142zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A tight lower bound for planar Steiner orientation

Cited in

(4)

• A tight lower bound for planar Steiner orientation
• Steiner hull algorithm for the uniform orientation metrics
• A tight lower bound for edge-disjoint paths on planar DAGs
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625142)