A tight lower bound for planar Steiner orientation

DOI10.1007/s00453-019-00580-xzbMath1425.68307OpenAlexW2944399784MaRDI QIDQ1999967

Rajesh Chitnis, Ondřej Suchý, Andreas Emil Feldmann

Publication date: 27 June 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00580-x

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 ⋮ To close is easier than to open: dual parameterization to \(k\)-median

Cites Work

• Unnamed Item
• Unnamed Item
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
• Strong computational lower bounds via parameterized complexity
• On orientations and shortest paths
• Which problems have strongly exponential complexity?
• A tight lower bound for Steiner orientation
• A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Directed multicut is W[1-hard, even for four terminal pairs]
• Improved Orientations of Physical Networks
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
• Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
• Parameterized Algorithms
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Steiner Forest Orientation Problems
• On the complexity of \(k\)-SAT
• A note on orientations of mixed graphs

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