A highly efficient algorithm for maximum cut on Halin graphs

DOI10.13471/J.CNKI.ACTA.SNUS.2019.04.009MaRDI QIDQ5209129zbMATH OpenOpenAlexFDO

Authors Li Xu, Dingjun Lou, Yifan Jiang, Zongrong Qin

Publication date 22 January 2020

Full work available at URL http://xuebao.sysu.edu.cn/Jweb_zrb/EN/10.13471/j.cnki.acta.snus.2019.04.009

zbMATH Keywords

maximum cutextendibleodd faceshrinking fan

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Partitioning planar graphs: a fast combinatorial approach for max-cut
• A linear time algorithm for graph partition problems
• An exact algorithm for MAX-CUT in sparse graphs
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs

This page was built for publication: A highly efficient algorithm for maximum cut on Halin graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5209129)