On the complexity of locally rainbow path

DOI10.1007/978-3-032-04700-7_12MaRDI QIDQ6852231zbMATH OpenFDO

Authors Hiroshi Eto, Tesshu Hanaka, Eiji Miyano, Shuya Yoshida

Publication date 26 February 2026

Full work available at URL https://doi.org/10.1007/978-3-032-04700-7_12

zbMATH Keywords

locally rainbow pathparameterized algorithmshortest \(s\)-\(t\) path

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Colored Path Problem and Its Applications
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Color-coding
• Easy problems for tree-decomposable graphs
• Elements of finite model theory.
• Fixed-parameter tractability of maximum colored path and beyond
• Further hardness results on rainbow and strong rainbow connectivity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On finding rainbow and colorful paths
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Optimal colorings with rainbow paths
• Parameterized algorithms
• Rainbow connections of graphs: a survey
• Sparsity. Graphs, structures, and algorithms
• The complexity of determining the rainbow vertex-connection of a graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The rainbow connectivity of a graph
• The structural complexity landscape of finding balance-fair shortest paths
• Tropical paths in vertex-colored graphs

This page was built for publication: On the complexity of locally rainbow path

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