Path-driven orientation of mixed graphs

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

zbMATH Keywords

algorithmic complexitymixed graphsgraph orientationbiological networks

Mathematics Subject Classification ID

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

Graphical characterization of positive definite non symmetric quasi-Cartan matrices

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