On the connection between interval size functions and path counting

DOI10.1007/S00037-016-0137-8MaRDI QIDQ2410681zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• On the Connection between Interval Size Functions and Path Counting
• The Complexity of Counting Functions with Easy Decision Version
• Completeness results for counting problems with easy decision
• The Complexity of Computing the Size of an Interval
• scientific article; zbMATH DE number 1754654

Cites work

• scientific article; zbMATH DE number 1953880 (Why is no real title available?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A very hard log-space counting class
• Counting independent sets up to the tree threshold
• Descriptive complexity of \(\#\)P functions
• FPTAS for counting weighted edge covers
• Monte-Carlo approximation algorithms for enumeration problems
• On the Connection between Interval Size Functions and Path Counting
• PP is as Hard as the Polynomial-Time Hierarchy
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• The Complexity of Computing the Size of an Interval
• The Complexity of Counting Functions with Easy Decision Version
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity theory companion
• The operators min and max on the polynomial hierarchy
• The relative complexity of approximate counting problems

Cited in

(6)

• On the Connection between Interval Size Functions and Path Counting
• The Complexity of Counting Functions with Easy Decision Version
• Completeness results for counting problems with easy decision
• Completeness, approximability and exponential time results for counting problems with easy decision version
• The Complexity of Computing the Size of an Interval
• scientific article; zbMATH DE number 1754654 (Why is no real title available?)

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

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