Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
From MaRDI portal
Publication:820146
DOI10.1016/j.tcs.2005.10.004zbMath1087.68067OpenAlexW2108078607MaRDI QIDQ820146
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
Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing, Multistage graph problems on a global budget, Isolation concepts for efficiently enumerating dense subgraphs, On the fixed-parameter tractability of the equivalence test of monotone normal forms, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Paradigms for parameterized enumeration, Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing, Extension of some edge graph problems: standard, parameterized and approximation complexity, Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU, Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, Vertex cover problem parameterized above and below tight bounds, Invited talks, Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space, A cubic-vertex kernel for flip consensus tree, Towards optimal and expressive kernelization for \(d\)-hitting set, Computational aspects of monotone dualization: a brief survey, Refined notions of parameterized enumeration kernels with applications to matching cut enumeration, Fixed-parameter enumerability of cluster editing and related problems, Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover, Complexity of independency and cliquy trees, COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY, Extended formulations for vertex cover, Parameterized Enumeration for Modification Problems, On the threshold of intractability, Vertex and edge covers with clustering properties: Complexity and algorithms, Lower bounds for three algorithms for transversal hypergraph generation, On the complexity of solution extension of optimization problems, The union of minimal hitting sets: parameterized combinatorial bounds and counting, THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS, Dynamic kernels for hitting sets and set packing, Parameterizations of hitting set of bundles and inverse scope, An average study of hypergraphs and their minimal transversals
Cites Work
- An efficient fixed-parameter algorithm for 3-hitting set
- A theory of diagnosis from first principles
- On generating all maximal independent sets
- The complexity of reconstructing trees from qualitative characters and subtrees
- Automated generation of search tree algorithms for hard graphs modification problems
- New methods for 3-SAT decision and worst-case analysis
- Vertex Cover: Further Observations and Further Improvements
- On the Generality of Phylogenies from Incomplete Directed Characters
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Vertex packings: Structural properties and algorithms
- Nondeterminism within $P^ * $
- 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
- Generating dual-bounded hypergraphs
- A Polynomial-Time Algorithm for Near-Perfect Phylogeny
- Exact algorithms for finding minimum transversals in rank-3 hypergraphs
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Two strikes against perfect phylogeny
- Parameterized and Exact Computation
- Efficient algorithms for inferring evolutionary trees
- SOFSEM 2004: Theory and Practice of Computer Science
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
