Name
Abstract | ||
|---|---|---|
An acyclic subhypergraph of a hypergraph is maximal if there exists no acyclic subhypergraph containing it. In this paper, first we show that, unless P=NP, there is no polynomial delay algorithm for generating all maximal acyclic subhypergraphs in lexicographic order . Next, by ignoring the order of outputs, we design a polynomial delay algorithm for generating all maximal acyclic subhypergraphs. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-540-95891-8_19 | SOFSEM |
Keywords | Field | DocType |
acyclic subhypergraph,maximal acyclic subhypergraphs,polynomial delay,polynomial delay algorithm,lexicographic order | Discrete mathematics,Combinatorics,Polynomial,Existential quantification,Hypergraph,Lexicographical order,Mathematics | Conference |
Volume | ISSN | Citations |
5404 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Taishin Daigo | 1 | 1 | 0.35 |
| Kouichi Hirata | 2 | 130 | 32.04 |