Counting on rainbow k-connections

DOI10.1007/978-981-97-2340-9_23MaRDI QIDQ6636091zbMATH OpenFDO

Authors Robert D. Barish, Tetsuo Shibuya

Publication date 12 November 2024

zbMATH Keywords

fixed-parameter tractabilityedge colorings\#PFPTapproximation hardnessNPproper connected coloringsrainbow connected coloringstreewidth FPT

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Easy problems for tree-decomposable graphs
• Fundamentals of parameterized complexity
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• Graph theory
• Graph theory with applications
• Hardness and algorithms for rainbow connection
• On Unapproximable Versions of $NP$-Complete Problems
• On proper-path colorings in graphs
• On the (di)graphs with (directed) proper connection number two
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Predecessor existence problems for finite discrete dynamical systems
• Proper connection of graphs
• Rainbow connection in graphs
• Rainbow connectivity: hardness and tractability
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• The rainbow connectivity of a graph
• The relative complexity of approximate counting problems

This page was built for publication: Counting on rainbow \(k\)-connections

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