Polynomial time algorithms for two classes of subgraph problem
RAIRO - Operations Research (2008)
- Volume: 42, Issue: 3, page 291-298
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topSridharan, Sriraman. "Polynomial time algorithms for two classes of subgraph problem." RAIRO - Operations Research 42.3 (2008): 291-298. <http://eudml.org/doc/250400>.
@article{Sridharan2008,
abstract = {
We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K1,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 K1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.
},
author = {Sridharan, Sriraman},
journal = {RAIRO - Operations Research},
keywords = {Polynomial time algorithm; NP-complete; graph; star; regular graph; perfect marching.; polynomial time algorithm; perfect matching},
language = {eng},
month = {8},
number = {3},
pages = {291-298},
publisher = {EDP Sciences},
title = {Polynomial time algorithms for two classes of subgraph problem},
url = {http://eudml.org/doc/250400},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Sridharan, Sriraman
TI - Polynomial time algorithms for two classes of subgraph problem
JO - RAIRO - Operations Research
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 291
EP - 298
AB -
We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K1,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 K1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.
LA - eng
KW - Polynomial time algorithm; NP-complete; graph; star; regular graph; perfect marching.; polynomial time algorithm; perfect matching
UR - http://eudml.org/doc/250400
ER -
References
top- A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data structures and algorithms, Addison-Wesley, Reading, Mass (1983).
- C. Berge, Graphes, Gauthier-Villars, Paris (1983).
- J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Macmillan, London (1978).
- V. Chvàtal, H. Fleishner, J. Sheehan and C. Thomassen, Three-regular subgraphs of four regular graphs. J. Graph Theor. 3 (1979) 371–386.
- J. Edmonds, Paths, trees and flowers. Can. J. Math.17 (1965) 449–467.
- 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).
- M. Las Vergnas, A note on matchings in graphs. Cahiers du Centre d'Etudes de Recherche Opérationnelle17 (1975) 257–260.
- 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.
- Sriraman Sridharan, A note on regular subgraphs of regular graphs. J. Math. Phys. Sci.28 (5) (1994) 237–241.
- V.A. Tashkinov, Regular subgraphs of regular graphs. Soviet. Math. Dokl. Vol. 26 (1982).
- W.T. Tutte, The factorization of linear graphs. J. London Math. Soc.22 (1947) 107–111.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.