On Counting Parameterized Matching and Packing

DOI10.1007/978-3-319-39817-4_13zbMATH Open1475.68248OpenAlexW2493989425MaRDI QIDQ4632178FDOQ4632178

Authors: Yunlong Liu, Jianxin Wang 

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_13

Recommendations

• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem
• On counting 3-D matchings of size \(k\)
• scientific article; zbMATH DE number 1979521
• Counting matchings of size \(k\) is \#W[1]-hard

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Improved algorithms for path, matching, and packing problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Counting Paths and Packings in Halves
• Monte-Carlo approximation algorithms for enumeration problems
• The Parameterized Complexity of Counting Problems
• The parameterised complexity of counting connected subgraphs and graph motifs
• Title not available (Why is that?)
• Parameterized counting problems
• Parameterized and Exact Computation
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Counting matchings of size \(k\) is \#W[1]-hard
• On counting 3-D matchings of size \(k\)
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum

Cited In (9)

• Parameterized algorithms for weighted matching and packing problems
• Weighted counting of \(k\)-matchings is \#W[1]-hard
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Algorithms and Data Structures
• Title not available (Why is that?)
• On counting 3-D matchings of size \(k\)
• Counting matchings of size \(k\) is \#W[1]-hard
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
• A Randomized Approximation Algorithm for Parameterized 3-D Matching Counting Problem

This page was built for publication: On Counting Parameterized Matching and Packing

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