Finding and counting permutations via CSPs
From MaRDI portal
Publication:2041985
DOI10.1007/S00453-021-00812-ZOpenAlexW3133527322MaRDI QIDQ2041985FDOQ2041985
Authors: Benjamin Aram Berendsohn, László Kozma, Dániel Marx 
Publication date: 26 July 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.04673
Recommendations
- Finding and Counting Permutations via CSPs
- The complexity of counting poset and permutation patterns
- On exact algorithms for the permutation CSP
- Counting solutions to CSP using generating polynomials
- Computable permutations and word problems
- Counting fixed-length permutation patterns
- Counting permutations by numbers of excedances, fixed points and cycles
- Counting and generating permutations in regular classes
- Counting Pop-Stacked Permutations in Polynomial Time
- scientific article; zbMATH DE number 91009
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Restricted permutations
- A partial k-arboretum of graphs with bounded treewidth
- Can you beat treewidth?
- Title not available (Why is that?)
- On two techniques of combining branching and treewidth
- Title not available (Why is that?)
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Patterns in permutations and words.
- Pattern matching for \(k\)-track permutations
- Finding pattern matchings for permutations
- Pattern matching for permutations
- Pattern matching for 321-avoiding permutations
- Title not available (Why is that?)
- Hardness of permutation pattern matching
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- Parallel algorithms for separable permutations
- The computational landscape of permutation patterns
- A fast algorithm for permutation pattern matching based on alternating runs
- On Complexity of the Subpattern Problem
- Title not available (Why is that?)
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- Title not available (Why is that?)
- Finding small patterns in permutations in linear time
- Sorting Using Networks of Queues and Stacks
- Tree clustering for constraint networks
- Estimating the Efficiency of Backtrack Programs
- A survey of stack-sorting disciplines
- Permutations sortable by two stacks in parallel and quarter plane walks
- Permutation classes
- Pathwidth of cubic graphs and exact algorithms
- A walk through combinatorics. An introduction to enumeration and graph theory
- Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
- On a unimodal sequence of binomial coefficients
- Testing for forbidden order patterns in an array
- Title not available (Why is that?)
- Sorting jordan sequences in linear time using level-linked search trees
- Self-adjusting binary search trees: what makes them tick?
- Hitting Set for hypergraphs of low VC-dimension
- Structure of graphs with locally restricted crossings
- Fast Sorting and Pattern-Avoiding Permutations
- Generating permutations with restricted containers
- Permutation pattern matching in \((213,231)\)-avoiding permutations
- Improving TSP tours using dynamic programming over tree decompositions
- Bounds for the growth rate of meander numbers
- The complexity of pattern matching for 321-avoiding and skew-merged permutations
- Improved bounds for testing forbidden order patterns
Cited In (14)
- On exact algorithms for the permutation CSP
- Strongly sublinear algorithms for testing pattern freeness
- Title not available (Why is that?)
- Parity permutation pattern matching
- Finding and Counting Permutations via CSPs
- Finding and counting permutations via CSPs
- Counting and Generating Permutations Using Timed Languages
- Finding small patterns in permutations in linear time
- Parity permutation pattern matching
- The complexity of counting poset and permutation patterns
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Permutation patterns are hard to count
- Algorithms for testing occurrences of length 4 patterns in permutations
- Title not available (Why is that?)
Uses Software
This page was built for publication: Finding and counting permutations via CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2041985)
