Cited By
View all- Siddiqi MHaque MShahin MHossan M(2005)Spanning trees with restricted degrees for series-parallel graph2005 IEEE International Conference on Granular Computing10.1109/GRC.2005.1547279(256-258 Vol. 1)Online publication date: 2005
Degree restricted spanning trees of graphs
Pages 225 - 228
Abstract
Let G = (V, E) be a connected graph and X be a vertex subset of G. Let f be a mapping from X to the set of natural numbers such that f(x) ≥ 2 for all x σ X. A degree restricted spanning tree is a spanning tree T of G such that f(x) ≤ degT(x) for all x σ X, where degT(x) denotes the degree of a vertex x in T. In this paper, we show that the decision problem "whether there exists a degree restricted spanning tree in G" is NP-complete. We also give a restricted proof of a conjecture, provided by Kaneko and Yoshimoto, on the existence of such a spanning tree in general graphs. Finally, we present a polynomial-time algorithm to find a degree restricted spanning tree of a graph satisfying the conditions presented in the restricted proof of the conjecture.
References
[1]
Akiyama, J., and Kano, M. Factors and Factorizations of graphs - A survey. J. Graph Theory, 9 (1985), 1--42.
[2]
Böhme, T., Broersma, H.J., Göbel, F., Kostochka, A. V., and Stiebitz, M. Spanning trees with pairwise nonadjacent endvertices. Discrete Math., 170 (1997), 219--222.
[3]
Garey, M.R., and Johnson, D.S. Computers and Intractability. Freeman, New York, 1979.
[4]
Hall, P. On representation of subsets. J. London Math Soc., 10 (1935), 26--30.
[5]
Hopcraft, J., and Karp, R. M., An O (n2.5) algorithm for maximum matching in bipartite graphs. SIAM J. Computing, 2 (1973), 225--231.
[6]
Kaneko, A., and Yoshimoto, K. On spanning trees with restricted degrees. Information Processing Letters, 73 (2000), 163--165.
Index Terms
- Degree restricted spanning trees of graphs
Recommendations
Low-Degree Spanning Trees of Small Weight
Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Tree spanners on chordal graphs: complexity and algorithms
A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREE t-SPANNER problem asks whether a graph admits a tree t-spanner, given t. We substantially ...
A limit characterization for the number of spanning trees of graphs
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {Gn} be a sequence of graphs G0, G1, G2.... that belong to a particular class. We consider graphs of the form Kn -...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2004
1733 pages
ISBN:1581138121
DOI:10.1145/967900
- Conference Chair:
- Hisham M. Haddad,
- Program Chairs:
- Andrea Omicini,
- Roger L. Wainwright,
- Publications Chair:
- Lorie M. Liebrock
Copyright © 2004 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 March 2004
Check for updates
Author Tags
Qualifiers
- Article
Conference
SAC04
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 463Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
Cited By
View all- Siddiqi MHaque MShahin MHossan M(2005)Spanning trees with restricted degrees for series-parallel graph2005 IEEE International Conference on Granular Computing10.1109/GRC.2005.1547279(256-258 Vol. 1)Online publication date: 2005
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in