Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
From MaRDI portal
Publication:820146
DOI10.1016/J.TCS.2005.10.004zbMATH Open1087.68067OpenAlexW2108078607MaRDI QIDQ820146FDOQ820146
Publication date: 6 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.004
Recommendations
Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Automated generation of search tree algorithms for hard graphs modification problems
- The complexity of reconstructing trees from qualitative characters and subtrees
- A theory of diagnosis from first principles
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient algorithms for inferring evolutionary trees
- On generating all maximal independent sets
- Nondeterminism within $P^ * $
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Title not available (Why is that?)
- Vertex cover: Further observations and further improvements
- New methods for 3-SAT decision and worst-case analysis
- Title not available (Why is that?)
- Two strikes against perfect phylogeny
- An efficient fixed-parameter algorithm for 3-hitting set
- Exact algorithms for finding minimum transversals in rank-3 hypergraphs
- Title not available (Why is that?)
- A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
- A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Generating dual-bounded hypergraphs
- A Polynomial-Time Algorithm for Near-Perfect Phylogeny
- Title not available (Why is that?)
- On the Generality of Phylogenies from Incomplete Directed Characters
- Title not available (Why is that?)
- Title not available (Why is that?)
- SOFSEM 2004: Theory and Practice of Computer Science
Cited In (38)
- Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
- Dynamic kernels for hitting sets and set packing
- Parameterized and Exact Computation
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- On the complexity of solution extension of optimization problems
- Multistage graph problems on a global budget
- Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing
- Lower bounds for three algorithms for transversal hypergraph generation
- Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
- An impossibility result for phylogeny reconstruction from \(k\)-mer counts
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Title not available (Why is that?)
- An average study of hypergraphs and their minimal transversals
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Parameterized Enumeration for Modification Problems
- Paradigms for parameterized enumeration
- A cubic-vertex kernel for flip consensus tree
- Performance of matrix representation with parsimony for inferring species from gene trees
- On the fixed-parameter tractability of the equivalence test of monotone normal forms
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- Extended formulations for vertex cover
- On the threshold of intractability
- Fixed-parameter enumerability of cluster editing and related problems
- Parameterizations of hitting set of bundles and inverse scope
- Space-efficient graph kernelizations
- Computational aspects of monotone dualization: a brief survey
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover
- Towards optimal and expressive kernelization for \(d\)-hitting set
- COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY
- Isolation concepts for efficiently enumerating dense subgraphs
- Invited talks
- Complexity of independency and cliquy trees
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
- Vertex cover problem parameterized above and below tight bounds
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
This page was built for publication: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820146)
