Back to Search
Start Over
Counting Minimal Transversals of β-Acyclic Hypergraphs
- Source :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, 2019, ⟨10.1016/j.jcss.2018.10.002⟩, Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.10.002⟩, CoRR, CoRR, 2018, abs/1808.05017
- Publication Year :
- 2019
- Publisher :
- HAL CCSD, 2019.
-
Abstract
- International audience; We prove that one can count in polynomial time the number of minimal transversalsof β-acyclic hypergraphs. In consequence, we can count in polynomial timethe number of minimal dominating sets of strongly chordal graphs, continuingthe line of research initiated in [M.M. Kanté and T. Uno, Counting MinimalDominating Sets, TAMC'17].
- Subjects :
- [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
General Computer Science
Computer Networks and Communications
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Dominating sets
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Theoretical Computer Science
Combinatorics
Chordal graph
020204 information systems
Computer Science - Data Structures and Algorithms
0202 electrical engineering, electronic engineering, information engineering
Strongly chordal graphs
Time complexity
Computer Science::Databases
Mathematics
Applied Mathematics
β-Acyclic Hypergraphs
Computational Theory and Mathematics
Counting problem
010201 computation theory & mathematics
Line (geometry)
Minimal transversals
Subjects
Details
- Language :
- English
- ISSN :
- 00220000 and 10902724
- Database :
- OpenAIRE
- Journal :
- Journal of Computer and System Sciences, Journal of Computer and System Sciences, 2019, ⟨10.1016/j.jcss.2018.10.002⟩, Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.10.002⟩, CoRR, CoRR, 2018, abs/1808.05017
- Accession number :
- edsair.doi.dedup.....d2b5bf22d1e90aa890567d5c92dbf0ef