A linear time algorithm for balance vertices on trees

A linear time algorithm for balance vertices on trees. Pham, V. H., Nguyen, K. T., & Le, T. T. Discrete Optimization, 32:37–42, 2019.

Paper doi abstract bibtex

The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.

@article{DBLP:journals/disopt/PhamNL19,
	title = {A linear time algorithm for balance vertices on trees},
	volume = {32},
	issn = {15725286},
	url = {https://doi.org/10.1016/j.disopt.2018.11.001},
	doi = {10.1016/j.disopt.2018.11.001},
	abstract = {The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.},
	journal = {Discrete Optimization},
	author = {Pham, Van Huy and Nguyen, Kien Trung and Le, Tran Thu},
	year = {2019},
	keywords = {Balance vertices, Complexity, Tree},
	pages = {37--42},
}

Downloads: 0

{"_id":"ZfzjZjCbpB4ezgBNC","bibbaseid":"pham-nguyen-le-alineartimealgorithmforbalanceverticesontrees-2019","author_short":["Pham, V. H.","Nguyen, K. T.","Le, T. T."],"bibdata":{"bibtype":"article","type":"article","title":"A linear time algorithm for balance vertices on trees","volume":"32","issn":"15725286","url":"https://doi.org/10.1016/j.disopt.2018.11.001","doi":"10.1016/j.disopt.2018.11.001","abstract":"The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.","journal":"Discrete Optimization","author":[{"propositions":[],"lastnames":["Pham"],"firstnames":["Van","Huy"],"suffixes":[]},{"propositions":[],"lastnames":["Nguyen"],"firstnames":["Kien","Trung"],"suffixes":[]},{"propositions":[],"lastnames":["Le"],"firstnames":["Tran","Thu"],"suffixes":[]}],"year":"2019","keywords":"Balance vertices, Complexity, Tree","pages":"37–42","bibtex":"@article{DBLP:journals/disopt/PhamNL19,\n\ttitle = {A linear time algorithm for balance vertices on trees},\n\tvolume = {32},\n\tissn = {15725286},\n\turl = {https://doi.org/10.1016/j.disopt.2018.11.001},\n\tdoi = {10.1016/j.disopt.2018.11.001},\n\tabstract = {The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.},\n\tjournal = {Discrete Optimization},\n\tauthor = {Pham, Van Huy and Nguyen, Kien Trung and Le, Tran Thu},\n\tyear = {2019},\n\tkeywords = {Balance vertices, Complexity, Tree},\n\tpages = {37--42},\n}\n\n","author_short":["Pham, V. H.","Nguyen, K. T.","Le, T. T."],"key":"DBLP:journals/disopt/PhamNL19","id":"DBLP:journals/disopt/PhamNL19","bibbaseid":"pham-nguyen-le-alineartimealgorithmforbalanceverticesontrees-2019","role":"author","urls":{"Paper":"https://doi.org/10.1016/j.disopt.2018.11.001"},"keyword":["Balance vertices","Complexity","Tree"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://api.zotero.org/groups/2168152/items?key=VCdsaROd5deDY3prqqG8kI0c&format=bibtex&limit=100","dataSources":["syJjwTDDM32TsM2iF","QwrFbRJvXF69SEShv","HbngRCZLbLed2q9QT","LtEFvT85hYpNg4Esp","iHfnnAr7wKJJxkNMt","PrvBTxn4Zgeep29e5","78Yd9ZHcx783Wkffe","SKRhTA7ok4L4waPkZ","GfrMfnKTkYdcYTRsy","RqqCdXGEyWH4dZ76k","cbiwaQPQJSZeJDDY9","2Jak7xK39ytqcgqQ4","CDfDBPD6CDScj6Ty4","WgiCycoQjRx6KArBy","KBdipwowTNXWiKqYd","yjd6eECyb3TYZpZ3R","D9jmZ7aoHfJnYQ4ES","R8dLFAvyQ2oFRijDJ","dc6SzEK4S9LfC3XpA","kGWABmrDfhF29uibh","YE9GesxGLCsBc3vvC","v3qfuosZ66nvD85FK","BSxBG5ms26R2teZn9"],"keywords":["balance vertices","complexity","tree"],"search_terms":["linear","time","algorithm","balance","vertices","trees","pham","nguyen","le"],"title":"A linear time algorithm for balance vertices on trees","year":2019}