The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
type: Item
instance of: scholarly article
title: The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
DOI: 10.1007/978-3-031-49614-1_8
author: Robert D. Barish
author: Tetsuo Shibuya
publication date: 2024-09-16T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7914097
zbMATH Keywords: proper connected coloring
zbMATH Keywords: edge coloring
zbMATH Keywords: counting complexity
zbMATH Keywords: approximate counting
zbMATH Keywords: exponential time hypothesis (ETH)
zbMATH Keywords: counting exponential time hypothesis (\#ETH)
zbMATH Keywords: \textit{NP}
zbMATH Keywords: \textit{\#P}
MaRDI profile type: MaRDI publication profile
cites work: Models and solution techniques for frequency assignment problems
cites work: Paths and trails in edge-colored graphs
cites work: On proper-path colorings in graphs
cites work: Alternating cycles and paths in edge-coloured multigraphs: A survey
cites work: Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
cites work: Q6126505
cites work: Q3097395
cites work: Proper connection of graphs
cites work: Rainbow connection in graphs
cites work: The rainbow connectivity of a graph
cites work: Q4836076
cites work: Exponential Time Complexity of the Permanent and the Tutte Polynomial
cites work: Fine-Grained Reductions from Approximate Counting to Decision
cites work: Graph Theory
cites work: On the (di)graphs with (directed) proper connection number two
cites work: Paths, Trees, and Flowers
cites work: Proper connection with many colors
cites work: Inapproximability of the Tutte polynomial
cites work: Proper connection number of random graphs
cites work: Minimum degree condition for proper connection number 2
cites work: Hardness results for three kinds of colored connections of graphs
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
cites work: Characterizations of graphs having large proper connection numbers
cites work: Alternating paths in edge-colored complete graphs
cites work: Zur allgemeinen Kurventheorie.
cites work: Julius Petersen's theory of regular graphs
cites work: The theory of regular graphs
cites work: Finding paths in graphs avoiding forbidden transitions
cites work: The Factors of Graphs
cites work: The method of alternating paths
cites work: Chromatic scheduling and frequency assignment
cites work: A note on alternating cycles in edge-coloured graphs
description: scientific article; zbMATH DE number 7914097