Algorithm on rainbow connection for maximal outerplanar graphs

DOI10.1016/j.tcs.2016.08.020zbMath1358.05161arXiv1605.01857OpenAlexW2964191086MaRDI QIDQ517025

Hengzhe Li, Xing-Chao Deng, Gui Ying Yan

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.01857

zbMATH Keywords

algorithmdiameterrainbow connection numbermaximal outerplanar graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (2)

Rainbow vertex-connection number on a small-world Farey graph ⋮ Delta invariant for Eulerian digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rainbow connection of graphs with diameter 2
• Rainbow connection number and connectivity
• Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs
• Further hardness results on rainbow and strong rainbow connectivity
• Computation of the center and diameter of outerplanar graphs
• Note on the hardness of rainbow connections for planar and line graphs
• Rainbow connection number and connected dominating sets
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• Rainbow connection in graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Oriented diameter and rainbow connection number of a graph

This page was built for publication: Algorithm on rainbow connection for maximal outerplanar graphs