{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T02:56:40Z","timestamp":1791601000742,"version":"4.3.4"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540438649","type":"print"},{"value":"9783540454656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_31","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"355-365","source":"Crossref","is-referenced-by-count":36,"title":["Spanning Trees with Bounded Number of Branch Vertices"],"prefix":"10.1007","author":[{"given":"Luisa","family":"Gargano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavol","family":"Hell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ladislav","family":"Stacho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ugo","family":"Vaccaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"M. Ali, Transmission Efficient Design and Management of Wavelength-Routed Optical Networks, Kluwer Academic Publishing, 2001.","DOI":"10.1007\/978-1-4615-1491-6"},{"key":"31_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/BFb0028567","volume-title":"Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science","author":"C. Bazgan","year":"1998","unstructured":"C. Bazgan, M. Shanta, Z. Tuza, \u201cOn the Approximability of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs\u201d, Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science, LNCS, Vol. 1373, 276\u2013286, Springer, (1998)."},{"key":"31_CR3","unstructured":"B. Beauquier, J-C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro, \u201cGraph Problems arising from Wavelength-Routing in All-Optical Networks\u201d, Proc. of WOCS, Geneve, Switzerland, 1997."},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1002\/jgt.3190200406","volume":"20","author":"C. G","year":"1995","unstructured":"G. Chen, R. H. Schelp, \u201cHamiltonicity for K1, r-free graphs\u201d, J. Graph Th., 20, 423\u2013439, 1995.","journal-title":"J. Graph Th."},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0012-365X(72)90079-9","volume":"2","author":"V. Chv\u00e1tal","year":"1972","unstructured":"V. Chv\u00e1tal, P. Erd\u0151s. \u201cA note on Hamiltonian circuits\u201d, Discr. Math., 2:111\u2013113, 1972.","journal-title":"Discr. Math."},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"2","author":"G. A. Dirac","year":"1952","unstructured":"G. A. Dirac, \u201cSome theorems on abstract graphs\u201d, Proc. London Math. Soc. 2:69\u201381, 1952.","journal-title":"Proc. London Math. Soc."},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"T. Feder, R. Motwani, C. Subi, \u201cFinding Long Paths and Cycles in Sparse Hamiltonian Graphs\u201d, Proc. Thirty second annual ACM Symposium on Theory of Computing (STOC\u201900) Portland, Oregon, May 21\u201323, 524\u2013529, ACM Press, 2000.","DOI":"10.1145\/335305.335368"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"L. Gargano, U. Vaccaro, \u201cRouting in All-Optical Networks: Algorithmic and Graph-Theoretic Problems\u201d, in: Numbers, Information and Complexity, I. Al-thofer et al. (Eds.), Kluwer Academic Publisher, pp. 555\u2013578, Feb. 2000.","DOI":"10.1007\/978-1-4757-6048-4_45"},{"issue":"2","key":"31_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/jgt.3190150204","volume":"15","author":"R. J. Gould","year":"1991","unstructured":"R. J. Gould. Updating the Hamiltonian problem\u2014a survey. J. Graph Theory, 15(2):121\u2013157, 1991.","journal-title":"J. Graph Theory"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"R. M. Karp, \u201cReducibility among combinatorial problems\u201d, Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (eds.), Plenum Press, (1972), 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"31_CR11","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1137\/S0097539794264585","volume":"25","author":"S. Khuller","year":"1996","unstructured":"S. Khuller, B. Raghavachari, N. Young, \u201cLow degree spanning trees of small weight\u201d, SIAM J. Comp., 25 (1996), 335\u2013368.","journal-title":"SIAM J. Comp."},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"J. K\u00f6nemann, R. Ravi, \u201cA Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees\u201d, Proc. Thirty second annual ACM Symp. on Theory of Computing (STOC\u201900), Portland, Oregon, 537\u2013546, (2000).","DOI":"10.1145\/335305.335371"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D. Krager","year":"1997","unstructured":"D. Krager, R. Motwani, D.S. Ramkumar, \u201cOn Approximating the Longest Path in a Graph\u201d, Algorithmica, 18 (1997), 82\u201398.","journal-title":"Algorithmica"},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s003730170059","volume":"17","author":"A. Kyaw","year":"2001","unstructured":"A. Kyaw, \u201cA Sufficient Condition for a Graph to have a k Tree\u201d, Graphs and Combinatorics, 17: 113\u2013121, 2001.","journal-title":"Graphs and Combinatorics"},{"key":"31_CR15","first-page":"1297","volume":"271","author":"M. Las Vergnas","year":"1971","unstructured":"M. Las Vergnas, \u201cSur une propriet\u00e9 des arbres maximaux dans un graphe\u201d, Compte Rendus Acad. Sc. Paris, 271, serie A, 1297\u20131300, 1971.","journal-title":"Compte Rendus Acad. Sc. Paris"},{"key":"31_CR16","first-page":"105","volume":"4","author":"Y. Liu","year":"1986","unstructured":"Y. Liu, F. Tian, and Z. Wu, \u201cSome results on longest paths and cycles in K1,3-free graphs\u201d, J. Changsha Railway Inst., 4:105\u2013106, 1986.","journal-title":"J. Changsha Railway Inst."},{"key":"31_CR17","first-page":"143","volume":"98","author":"L. R. Markus","year":"1993","unstructured":"L. R. Markus. Hamiltonian results in K1, r-free graphs. In Proc. of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton,FL, 1993), volume 98, pages 143\u2013149, 1993.","journal-title":"Proc. of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton,FL, 1993)"},{"issue":"2","key":"31_CR18","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1002\/jgt.3190090208","volume":"9","author":"M. M. Matthews","year":"1985","unstructured":"M. M. Matthews, D. P. Sumner. Longest paths and cycles in K1,3-free graphs. J. Graph Theory, 9(2):269\u2013277, 1985.","journal-title":"J. Graph Theory"},{"key":"31_CR19","volume-title":"Optical Communication Networks","author":"B. Mukherjee","year":"1997","unstructured":"B. Mukherjee, Optical Communication Networks, McGraw-Hill, New York, 1997."},{"issue":"1","key":"31_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01375473","volume":"11","author":"V. Neumann Lara","year":"1991","unstructured":"V. Neumann Lara, E. Rivera-Campo, \u201cSpanning trees with bounded degrees\u201d, Combinatorica, 11(1):55\u201361, 1991.","journal-title":"Combinatorica"},{"key":"31_CR21","doi-asserted-by":"publisher","first-page":"55","DOI":"10.2307\/2308928","volume":"67","author":"O. Ore","year":"1960","unstructured":"O. Ore. Note on Hamilton circuits. Amer. Math. Monthly, 67:55, 1960.","journal-title":"Amer. Math. Monthly"},{"key":"31_CR22","first-page":"266","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"B. Raghavari","year":"1997","unstructured":"B. Raghavari, \u201cAlgorithms for finding low-degree structures\u201d, in: Approximation Algorithms for NP-Hard Problems, D.S. Hochbaum (Ed.) PWS Publishing Company, Boston, 266\u2013295, 1997."},{"key":"31_CR23","unstructured":"L. Sahasrabuddhe, N. Singhal, B. Mukherjee, \u201cLight-Trees for WDM Optical Networks: Optimization Problem Formulations for Unicast and Broadcast Traffic,\u201c Proc. Int. Conf. on Communications, Computers, and Devices (ICCD-2000), IIT Kharagpur, India, (2000)."},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/35.747251","volume":"37","author":"L. H. Sahasrabuddhe","year":"1999","unstructured":"L. H. Sahasrabuddhe, B. Mukherjee, \u201cLight Trees: Optical Multicasting for Improved Performance in Wavelength-Routed Networks\u201c, IEEE Comm. Mag., 37: 67\u201373, 1999.","journal-title":"IEEE Comm. Mag."},{"key":"31_CR25","unstructured":"T.E. Sterne, K. Bala, MultiWavelength Optical Networks, Addison-Wesley, 1999."},{"key":"31_CR26","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0012-365X(74)90074-0","volume":"9","author":"C. Thomassen","year":"1974","unstructured":"C. Thomassen, \u201cHypohamiltonian and hypotraceable graphs\u201d, Disc. Math., 9(1974), 91\u201396.","journal-title":"Disc. Math."},{"issue":"1","key":"31_CR27","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0095-8956(81)90089-7","volume":"30","author":"C. Thomassen","year":"1981","unstructured":"C. Thomassen, \u201cPlanar cubic hypo-Hamiltonian and hypotraceable graphs\u201d, J. Combin. Theory Ser. B, 30(1), 36\u201344, 1981.","journal-title":"J. Combin. Theory Ser. B"},{"key":"31_CR28","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1109\/50.988983","volume":"20","author":"Y. Wang","year":"2002","unstructured":"Y. Wang, Y. Yang, \u201cMulticasting in a Class of Multicast\u2014Capable WDM Networks\u201d, Journal of Lightwave Technology, 20 (2002), 350\u2013359.","journal-title":"Journal of Lightwave Technology"},{"key":"31_CR29","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02995957","volume":"43","author":"S. Win","year":"1975","unstructured":"S. Win, \u201cExistenz von Ger\u00fcsten mit vorgeschriebenem Maximalgrad in Graphen\u201d, Abh. Mat. Sem. Univ. Hamburg, 43: 263\u2013267, 1975.","journal-title":"Abh. Mat. Sem. Univ. Hamburg"},{"key":"31_CR30","doi-asserted-by":"crossref","unstructured":"X. Zhang, J. Wei, C. Qiao, \u201cCostrained Multicast Routing in WDM Networks with Sparse Light Splitting\u201d, Proc. of IEEE INFOCOM 2000, vol. 3: 1781\u20131790, Mar. 2000.","DOI":"10.1109\/INFCOM.2000.832578"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:27:20Z","timestamp":1737052040000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}