On the connection between interval size functions and path counting

DOI10.1007/s00037-016-0137-8zbMath1401.68107OpenAlexW2478952343MaRDI QIDQ2410681

Evangelos Bampas, Aris Tentes, Aris Pagourtzis, Andreas Göbel

Publication date: 18 October 2017

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-016-0137-8

zbMATH Keywords

path countingcounting functionsfeasibility constraintseasy decisioninterval size functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Completeness Results for Counting Problems with Easy Decision ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• A very hard log-space counting class
• The relative complexity of approximate counting problems
• Descriptive complexity of \(\#\)P functions
• FPTAS for Counting Weighted Edge Covers
• Counting independent sets up to the tree threshold
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• PP is as Hard as the Polynomial-Time Hierarchy
• On the Connection between Interval Size Functions and Path Counting
• Monte-Carlo approximation algorithms for enumeration problems
• The Complexity of Enumeration and Reliability Problems
• THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY
• The Complexity of Computing the Size of an Interval
• The Complexity of Counting Functions with Easy Decision Version
• The complexity theory companion

This page was built for publication: On the connection between interval size functions and path counting