Geodesic
Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 225-241.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We study the minimum number of label transitions around a given vertex v0 in a planar multigraph G, in which the edges incident with v0 are labelled with integers 1, ..., l, and the minimum is taken over all embeddings of G in the plane. For a fixed number of labels, a linear-time fixed-parameter tractable algorithm that computes the minimum number of label transitions around v0 is presented. If the number of labels is unconstrained, then the problem of deciding whether the minimum number of label transitions is at most k is NP-complete.
DOI : 10.7155/jgaa.00256
Keywords: label transitions, planar graph, fixed-parameter tractable 
@article{JGAA_2012_16_2_a3,
     author = {Bojan Mohar and Petr \v{S}koda},
     title = {Minimizing the {Number} of {Label} {Transitions} {Around} a {Nonseparating} {Vertex} of a {Planar} {Graph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {225--241},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00256},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00256/}
}
TY  - JOUR
AU  - Bojan Mohar
AU  - Petr Škoda
TI  - Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 225
EP  - 241
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00256/
DO  - 10.7155/jgaa.00256
LA  - en
ID  - JGAA_2012_16_2_a3
ER  - 
%0 Journal Article
%A Bojan Mohar
%A Petr Škoda
%T Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph
%J Journal of Graph Algorithms and Applications
%D 2012
%P 225-241
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00256/
%R 10.7155/jgaa.00256
%G en
%F JGAA_2012_16_2_a3
Bojan Mohar; Petr Škoda. Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 225-241. doi : 10.7155/jgaa.00256. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00256/

Cité par Sources :