Directed Rank-Width and Displit Decomposition
作者： Mamadou Moustapha Kanté , Michaël Rao
DOI: 10.1007/978-3-642-11409-0_19
关键词: Block graph 、 Pathwidth 、 Cograph 、 Line graph 、 Split graph 、 Comparability graph 、 Discrete mathematics 、 Modular decomposition 、 Combinatorics 、 Indifference graph 、 Mathematics
摘要: Rank-width is a graph complexity measure that has many structural properties. It known the rank-width of an undirected maximum over all induced prime graphs with respect to split decomposition and at most 1 if only it distance-hereditary graph. We are interested in extension these results directed graphs. give several characterizations we prove displit decomposition, new on
springer.com
archives-ouvertes.fr
lirmm.fr 
sci-hub.st 参考文章(22)
R.H. Möhring, F.J. Radermacher, Substitution Decomposition for Discrete Structures and Connections with Combinatorial Optimization Algebraic and Combinatorial Methods in Operations Research, Proceedings of the Workshop on Algebraic Structures in Operations Research. ,vol. 95, pp. 257- 355 ,(1984) , 10.1016/S0304-0208(08)72966-9
Mamadou Moustapha Kanté, The rank-width of Directed Graphs ,(2007)
A Ehrenfeucht, T Harju, G Rozenberg, The Theory of 2-Structures WORLD SCIENTIFIC. ,(1999) , 10.1142/4197
Cyril Gavoille, Christophe Paul, Distance labeling scheme and split decomposition Discrete Mathematics. ,vol. 273, pp. 115- 130 ,(2003) , 10.1016/S0012-365X(03)00232-2
Csaba P. Gabor, Kenneth J. Supowit, Wen-Lian Hsu, Recognizing circle graphs in polynomial time Journal of the ACM. ,vol. 36, pp. 435- 473 ,(1989) , 10.1145/65950.65951
Bruno Courcelle, Stephan Olariu, Upper bounds to the clique width of graphs Discrete Applied Mathematics. ,vol. 101, pp. 77- 114 ,(2000) , 10.1016/S0166-218X(99)00184-5
Peter L. Hammer, Frédéric Maffray, Completely separable graphs Discrete Applied Mathematics. ,vol. 27, pp. 85- 99 ,(1990) , 10.1016/0166-218X(90)90131-U
Fabien de Montgolfier, Michaël Rao, The bi-join decomposition Electronic Notes in Discrete Mathematics. ,vol. 22, pp. 173- 177 ,(2005) , 10.1016/J.ENDM.2005.06.039
T. Gallai, Transitiv orientierbare Graphen Acta Mathematica Hungarica. ,vol. 18, pp. 25- 66 ,(1967) , 10.1007/BF02020961
J. Spinrad, Recognition of circle graphs Journal of Algorithms. ,vol. 16, pp. 264- 282 ,(1994) , 10.1006/JAGM.1994.1012