• DocumentCode
    498546
  • Title

    Colored Multiway Cuts in Generalized Tree Networks

  • Author

    Xiao, Xin ; Shuguang, Li

  • Author_Institution
    Coll. of Foreign Studies, Shandong Inst. of Bus. & Technol., Yantai, China
  • Volume
    1
  • fYear
    2009
  • fDate
    10-11 July 2009
  • Firstpage
    299
  • Lastpage
    301
  • Abstract
    Given a graph with color dependent edge weights and a partial coloration on some distinguished vertices, the colored multiway cut problem is to extend the partial coloration such that all the vertices are colored and the total weight of edges that have different colored endpoints is minimized. A polynomial time algorithm is presented that solves the problem exactly for generalized tree networks.
  • Keywords
    computational complexity; graph colouring; trees (mathematics); vertex functions; colored multiway cut problem; generalized tree networks; graph; partial coloration; polynomial time algorithm; vertices; Circuits; Computer science; Cost function; Database systems; Educational institutions; Network servers; Peer to peer computing; Polynomials; Tree graphs; algorithms; colored multiway cuts; generalized tree networks;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Information Engineering, 2009. ICIE '09. WASE International Conference on
  • Conference_Location
    Taiyuan, Shanxi
  • Print_ISBN
    978-0-7695-3679-8
  • Type

    conf

  • DOI
    10.1109/ICIE.2009.217
  • Filename
    5211046
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=498546