Zobrazeno 1 - 10
of 12
pro vyhledávání: '"Aanderaa–Karp–Rosenberg conjecture"'
Autor:
Jerson Borja, Andrés Angel
Publikováno v:
Journal of Graph Theory. 91:35-52
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9d20c6fc226c3d8488cb6bd3f980e950
https://doi.org/10.1002/jgt.22419
https://doi.org/10.1002/jgt.22419
Autor:
Bertrand Jouve, Etienne Fieux
Publikováno v:
Discrete Mathematics
Discrete Mathematics, Elsevier, In press, 343 (8)
Discrete Mathematics, 2020, 343 (8), ⟨10.1016/j.disc.2020.111914⟩
Discrete Mathematics, Elsevier, In press, 343 (8)
Discrete Mathematics, 2020, 343 (8), ⟨10.1016/j.disc.2020.111914⟩
Given a finite undirected graph $X$, a vertex is $0$-dismantlable if its open neighbourhood is a cone and $X$ is $0$-dismantlable if it is reducible to a single vertex by successive deletions of $0$-dismantlable vertices. By an iterative process, a v
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d41566c2469bedd1a5cb224252d97530
Autor:
Carl A. Miller
Publikováno v:
Foundations and Trends® in Theoretical Computer Science. 7:337-415
Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::64fde412b34294f8351d36a30ed354dc
https://doi.org/10.1561/0400000055
https://doi.org/10.1561/0400000055
Autor:
Eberhard Triesch, Torsten Korneffel
Publikováno v:
Combinatorica. 30:735-743
We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e12c030182701a650b60af10a08264fd
https://doi.org/10.1007/s00493-010-2485-3
https://doi.org/10.1007/s00493-010-2485-3
Autor:
Timothy Black
Publikováno v:
ITCS
A Boolean function in n variables is weakly evasive if its decision-tree complexity is Ω( n ). By k -graphs, we mean k -uniform hypergraphs. A k-graph property on v vertices is a Boolean function on n = v k variables corresponding to the k -subsets
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f723ed238ed2acc0c1a1eb81f741c509
https://doi.org/10.1145/2688073.2688085
https://doi.org/10.1145/2688073.2688085
Autor:
Frank H. Lutz
Publikováno v:
Journal of Combinatorial Theory, Series B. 81:110-124
The Evasiveness Conjecture for graph properties has natural generalizations to simplicial complexes and to set systems. In this paper we show that the Evasiveness Conjecture for simplicial complexes holds in dimension 2 and 3. We also present an infi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::141c0bb9aa640c76bf1e829e90458bb9
https://doi.org/10.1006/jctb.2000.2000
https://doi.org/10.1006/jctb.2000.2000
Autor:
Raghav Kulkarni
Publikováno v:
ITCS
A function f : {0, 1}n -> {0, 1} is called evasive if its decision tree complexity is maximal, i.e., D(f) = n. The long-standing Anderaa-Rosenberg-Karp (ARK) Conjecture asserts that every non-trivial monotone graph property is evasive. The Evasivenes
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5a1163c4dfc67e5b50fd4720a031ffad
https://doi.org/10.1145/2422436.2422454
https://doi.org/10.1145/2422436.2422454
Autor:
Andrew Chi-Chih Yao
Publikováno v:
SIAM Journal on Computing. 17:517-520
A Boolean function P from $\{ {0,1} \}^\prime $ into $\{ {0,1} \}$ is said to be evasive, if every decision-tree algorithm for evaluating P must examine all t arguments in the worst case. It was known that any nontrivial monotone bipartite graph prop
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::630923c45db6edd134dfc75a1021ad27
https://doi.org/10.1137/0217031
https://doi.org/10.1137/0217031
Autor:
Andrew Chi-Chih Yao
Publikováno v:
Journal of Computer and System Sciences. (3):267-287
For any property P on n-vertex graphs, let C(P) be the minimum number of edges needed to be examined by any decision tree algorithm for determining P. In 1975 Rivest and Vuillemin settled the Aanderra-Rosenberg Conjecture, proving that C(P)=Ω(n 2 )
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8a9333bc94ad1e63fcdf4a9e9dfc2bc8
Autor:
Ronald L. Rivest, Jean Vuillemin
Publikováno v:
Theoretical Computer Science. (3):371-384
A conjecture of Aanderaa and Rosenberg [15] motivates this work. We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b87c067b31e3a84ed7d6f8ac62c66b2b