Polynomial time algorithms for two classes of subgraph problem

Sridharan, Sriraman

doi:10.1051/ro:2008015

Sridharan, Sriraman

RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 291-298.

Résumé

We design a $O (n^{3})$ polynomial time algorithm for finding a $(k - 1)$ - regular subgraph in a $k$ -regular graph without any induced star $K_{1, 3}$ (claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of $k$ -regular graphs with an induced star $K_{1, 3}$ $(k e v e n, k \geq 6)$ , not containing any $(k - 1)$ -regular subgraph is also constructed.

MR Zbl

DOI : 10.1051/ro:2008015

Classification : 05C
Mots-clés : polynomial time algorithm, NP-complete, graph, star, regular graph, perfect marching

@article{RO_2008__42_3_291_0,
     author = {Sridharan, Sriraman},
     title = {Polynomial time algorithms for two classes of subgraph problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {291--298},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ro:2008015},
     mrnumber = {2444488},
     zbl = {1161.05344},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2008015/}
}

TY  - JOUR
AU  - Sridharan, Sriraman
TI  - Polynomial time algorithms for two classes of subgraph problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 291
EP  - 298
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2008015/
DO  - 10.1051/ro:2008015
LA  - en
ID  - RO_2008__42_3_291_0
ER  -

%0 Journal Article
%A Sridharan, Sriraman
%T Polynomial time algorithms for two classes of subgraph problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 291-298
%V 42
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2008015/
%R 10.1051/ro:2008015
%G en
%F RO_2008__42_3_291_0

Sridharan, Sriraman. Polynomial time algorithms for two classes of subgraph problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 291-298. doi : 10.1051/ro:2008015. http://archive.numdam.org/articles/10.1051/ro:2008015/

Bibliographie
Cité par

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data structures and algorithms, Addison-Wesley, Reading, Mass (1983). | MR | Zbl

[2] C. Berge, Graphes, Gauthier-Villars, Paris (1983). | MR | Zbl

[3] J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Macmillan, London (1978).

[4] V. Chvàtal, H. Fleishner, J. Sheehan and C. Thomassen, Three-regular subgraphs of four regular graphs. J. Graph Theor. 3 (1979) 371-386. | MR | Zbl

[5] J. Edmonds, Paths, trees and flowers. Can. J. Math. 17 (1965) 449-467. | MR | Zbl

[6] M.R. Garey and D.S. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness, W.H. Freeman and company, NY (1979). | MR | Zbl

[7] M. Las Vergnas, A note on matchings in graphs. Cahiers du Centre d'Etudes de Recherche Opérationnelle 17 (1975) 257-260. | MR | Zbl

[8] K.R. Parthasarathy and Sriraman Sridharan, On a generalization of Berge-Sauer conjecture, Combinatorics and Applications, edited by K.S. Vijayan and N.M. Singhi, Indian Stat. Institute, Calcutta (1982) 261-264. | MR | Zbl

[9] Sriraman Sridharan, A note on regular subgraphs of regular graphs. J. Math. Phys. Sci. 28 (5) (1994) 237-241. | MR | Zbl

[10] V.A. Tashkinov, Regular subgraphs of regular graphs. Soviet. Math. Dokl. Vol. 26 (1982). | Zbl

[11] W.T. Tutte, The factorization of linear graphs. J. London Math. Soc. 22 (1947) 107-111. | MR | Zbl

Cité par Sources :