Geodesic
The complexity of deciding whether a graph admits an orientation with fixed weak diameter
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most $k$, we call $\overrightarrow{G}$ $k$-weak (resp. $k$-strong). We consider several problems asking whether an undirected graph $G$ admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether $G$ admits a $k$-weak orientation is NP-complete for every $k \geq 2$. This notably implies the NP-completeness of several problems asking whether $G$ is an extremal graph (in terms of needed colours) for some vertex-colouring problems. 
@article{DMTCS_2016_17_3_a17,
     author = {Bensmail, Julien and Duvignau, Romaric and Kirgizov, Sergey},
     title = {The complexity of deciding whether a graph admits an orientation with fixed weak diameter},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2015-2016},
     volume = {17},
     number = {3},
     doi = {10.46298/dmtcs.2161},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2161/}
}
TY  - JOUR
AU  - Bensmail, Julien
AU  - Duvignau, Romaric
AU  - Kirgizov, Sergey
TI  - The complexity of deciding whether a graph admits an orientation with fixed weak diameter
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2161/
DO  - 10.46298/dmtcs.2161
LA  - en
ID  - DMTCS_2016_17_3_a17
ER  - 
%0 Journal Article
%A Bensmail, Julien
%A Duvignau, Romaric
%A Kirgizov, Sergey
%T The complexity of deciding whether a graph admits an orientation with fixed weak diameter
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 3
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2161/
%R 10.46298/dmtcs.2161
%G en
%F DMTCS_2016_17_3_a17
Bensmail, Julien; Duvignau, Romaric; Kirgizov, Sergey. The complexity of deciding whether a graph admits an orientation with fixed weak diameter. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3. doi: 10.46298/dmtcs.2161

Cité par Sources :