(Strong) conflict-free connectivity: algorithm and complexity

DOI10.1016/j.tcs.2019.10.043zbMath1436.68243arXiv1805.08072OpenAlexW2988316456WikidataQ126853019 ScholiaQ126853019MaRDI QIDQ2283032

Xiaoyu Zhu, Meng Ji, Xue Liang Li

Publication date: 27 December 2019

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

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

zbMATH Keywords

complexitypolynomial-time algorithmconflict-free connectionstrong conflict-free connection

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Conflict-free connection number of random graphs ⋮ Hardness results for three kinds of colored connections of graphs ⋮ Conflict-free (vertex)-connection numbers of graphs with small diameters ⋮ Strong conflict-free connection of graphs ⋮ On the \(k\)-component independence number of a tree ⋮ Some results on strong conflict-free connection number of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Proper connection of graphs
• Hardness and algorithms for rainbow connection
• Local optimization on graphs
• Edge ranking of graphs is hard
• Conflict-free connections of graphs
• Conflict-free connection numbers of line graphs
• On conflict-free connection of graphs
• Graphs with conflict-free connection number two
• Ordered colourings
• Rainbow connections of graphs: a survey
• Colorful monochromatic connectivity
• Conflict-free vertex-connections of graphs
• Rainbow connection in graphs
• Rankings of Graphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Maximum value of conflict-free vertex-connection number of graphs
• Properly Colored Connectivity of Graphs
• Conflict-Free Coloring and its Applications

This page was built for publication: (Strong) conflict-free connectivity: algorithm and complexity