Structural parameters for Steiner orientation

DOI10.4230/LIPICS.ISAAC.2025.38MaRDI QIDQ7364383zbMATH OpenFDO

Authors Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, Manolis Vasilakis

Publication date 1 October 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2025.38

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A faster algorithm for vertex cover parameterized by solution size
• A note on orientations of mixed graphs
• A partial k-arboretum of graphs with bounded treewidth
• A tight lower bound for planar Steiner orientation
• Approximation algorithms for orienting mixed graphs
• Complexity of automaton identification from given data
• Directed multicut is W[1]-hard, even for four terminal pairs
• Graph Classes: A Survey
• Improved approximation for orienting mixed graphs
• On orientations and shortest paths
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• Parameterized algorithms
• Parameterized inapproximability for Steiner orientation by gap amplification
• Steiner forest orientation problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

This page was built for publication: Structural parameters for Steiner orientation

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