The complexity of deciding whether a graph admits an orientation with fixed weak diameter

MaRDI QIDQ2808534zbMATH OpenFDO

Authors Julien Bensmail, Romaric Duvignau, Sergey Kirgizov

Publication date 24 May 2016

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2704/0.html

zbMATH Keywords

complexityoriented graphstrong diameterweak diameter

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12)

Recommendations

• The complexity of two graph orientation problems
• Complexity of approximating the oriented diameter of chordal graphs
• Weak diameter and cyclic properties in oriented graphs
• Diameter of orientations of graphs with given minimum degree
• scientific article; zbMATH DE number 1953095
• scientific article; zbMATH DE number 3991530
• On the dimension of oriented graphs
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• The diameter of an orientation of a complete multipartite graph
• The complexity of 2-vertex-connected orientation in mixed graphs

Cited in

(12)

• On oriented cliques with respect to push operation
• scientific article; zbMATH DE number 1953095 (Why is no real title available?)
• Efficient extraction algorithm for local fuzzy features of dynamic images
• Research on iterative repair algorithm of hyperchaotic image based on support vector machine
• Complete oriented colourings and the oriented achromatic number
• The complexity of two graph orientation problems
• Homomorphisms and colourings of oriented graphs: an updated survey
• Homomorphically full oriented graphs
• Complexity of approximating the oriented diameter of chordal graphs
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• On coloring parameters of triangle-free planar \((n, m)\)-graphs
• Outerplanar and planar oriented cliques

This page was built for publication: The complexity of deciding whether a graph admits an orientation with fixed weak diameter

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