Path-driven orientation of mixed graphs
From MaRDI portal
Publication:479025
DOI10.1016/j.dam.2014.10.016zbMath1304.05081OpenAlexW2064678289MaRDI QIDQ479025
Hafedh Mohamed-Babou, Irena Rusu, Guillaume Fertin
Publication date: 5 December 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.016
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Systems biology, networks (92C42)
Related Items
Cites Work
- Fundamentals of parameterized complexity
- A simplified NP-complete satisfiability problem
- Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
- On orientations and shortest paths
- Non deterministic polynomial optimization problems and their approximations
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Improved Approximation for Orienting Mixed Graphs
- Probability, ergodicity, irreversibility and dynamical systems
- Robbins's Theorem for Mixed Multigraphs
- Selecting an Optimum Configuration of One-Way and Two-Way Routes
- Distributed Algorithms For Unidirectional Networks
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Steiner Forest Orientation Problems
- A note on orientations of mixed graphs