Polynomial time algorithms for two classes of subgraph problem

Sridharan, Sriraman

doi:10.1051/ro:2008015

Geodesic

Parcourir par

Polynomial time algorithms for two classes of subgraph problem

Sridharan, Sriraman

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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :