Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

DOI10.1016/J.AML.2011.08.006MaRDI QIDQ427574zbMATH OpenOpenAlexFDO

Authors Xingchao Deng, Kai-Nan Xiang, Baoyindureng Wu

Publication date 14 June 2012

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2011.08.006

zbMATH Keywords

rainbow connection numberrainbow coloringmaximal cardinality searchmaximal outerplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Algorithm on rainbow connection for maximal outerplanar graphs
• Hardness and algorithms for rainbow connection
• Rainbow connectivity: hardness and tractability

Cites work

• scientific article; zbMATH DE number 1080085 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• scientific article; zbMATH DE number 3399275 (Why is no real title available?)
• Hardness and Algorithms for Rainbow Connectivity
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• Rainbow connection in graphs
• Rainbow connection in graphs with minimum degree three
• Rainbow connection number and connected dominating sets

Cited in

(6)

• scientific article; zbMATH DE number 6719578 (Why is no real title available?)
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Strong rainbow connection numbers of toroidal meshes
• An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs
• On the general position numbers of maximal outerplane graphs
• Algorithm on rainbow connection for maximal outerplanar graphs

This page was built for publication: Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

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