About: Aanderaa–Karp–Rosenberg conjecture

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

Unsolved problem on graph query complexity

Property	Value
dbo:description	unsolved problem on graph query complexity (en)
dbo:thumbnail	wiki-commons:Special:FilePath/Scorpion_graph.svg?width=300
dbo:wikiPageExternalLink	http://www.math.rutgers.edu/~saks/PUBS/dtsurvey.pdf https://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf http://portal.acm.org/citation.cfm%3Fid=1070591
dbo:wikiPageWikiLink	dbr:Multiset dbr:Glossary_of_graph_theory dbr:Simple_graph dbr:Undirected_graph dbc:Unsolved_problems_in_computer_science dbr:Graph_property dbc:Combinatorics dbr:Grover's_algorithm dbr:Centrum_Wiskunde_&_Informatica dbc:Graph_theory dbr:Conjecture dbr:Lecture_Notes_in_Computer_Science dbr:Deterministic_algorithm dbr:Dover_Publications dbr:Big_O_notation dbc:Computational_complexity_theory dbr:Monte_Carlo_algorithm dbr:Implicit_graph dbr:Algorithm dbc:Conjectures dbr:Topological_combinatorics dbr:Bipartite_graph dbr:Las_Vegas_algorithm dbr:Theoretical_computer_science dbr:Evasive_Boolean_function dbr:Richard_M._Karp dbr:Quantum_algorithm dbr:Complete_graph dbr:Erdős–Rényi_model dbr:Prime_power dbr:Journal_of_the_ACM dbr:Stål_Aanderaa dbr:Graph_(discrete_mathematics) dbr:Planar_graph dbr:Randomized_algorithm dbr:Society_for_Industrial_and_Applied_Mathematics dbr:Regular_graph dbr:Logical_disjunction dbr:Combinatorica dbr:Minor_(graph_theory) dbr:Hereditary_property dbr:Arnold_L._Rosenberg dbr:Journal_of_Computer_and_System_Sciences dbr:Springer-Verlag dbr:SIAM_Journal_on_Computing dbr:Richard_Karp dbr:Worst_case_analysis dbr:Query_complexity dbr:File:Scorpion_graph.svg dbr:Empty_graph dbr:Quantum_query_complexity dbr:SIGACT_News dbr:Subgraph_isomorphism dbr:Triangle_finding_problem
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Citation dbt:Cite_arXiv dbt:Refend dbt:Sfnp dbt:Refbegin dbt:Harvtxt dbt:Unsolved dbt:Short_description
dct:subject	dbc:Unsolved_problems_in_computer_science dbc:Combinatorics dbc:Computational_complexity_theory dbc:Conjectures dbc:Statements_in_graph_theory
gold:hypernym	dbr:Group
rdfs:label	Aanderaa–Karp–Rosenberg conjecture (en) Conjetura de Aanderaa-Karp-Rosenberg (es) Conjecture d'Aanderaa-Karp-Rosenberg (fr) Гипотеза Аандераа — Карпа — Розенберга (ru)
owl:sameAs	freebase:Aanderaa–Karp–Rosenberg conjecture wikidata:Aanderaa–Karp–Rosenberg conjecture dbpedia-fr:Aanderaa–Karp–Rosenberg conjecture dbpedia-es:Aanderaa–Karp–Rosenberg conjecture dbpedia-ru:Aanderaa–Karp–Rosenberg conjecture dbpedia-global:Aanderaa–Karp–Rosenberg conjecture dbr:Aanderaa–Karp–Rosenberg conjecture
prov:wasDerivedFrom	wikipedia-en:Aanderaa–Karp–Rosenberg_conjecture?oldid=1282405580&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Scorpion_graph.svg
foaf:isPrimaryTopicOf	wikipedia-en:Aanderaa–Karp–Rosenberg_conjecture
is dbo:knownFor of	dbr:Richard_M._Karp
is dbo:wikiPageDisambiguates of	dbr:Aanderaa
is dbo:wikiPageRedirects of	dbr:Aanderaa-Karp-Rosenberg_conjecture dbr:Aanderaa-Rosenberg_conjecture dbr:Aanderaa–Rosenberg_conjecture dbr:Evasiveness dbr:Evasiveness_conjecture
is dbo:wikiPageWikiLink of	dbr:List_of_Norwegian_mathematicians dbr:Decision_tree_model dbr:Clique_problem dbr:List_of_unsolved_problems_in_computer_science dbr:Implicit_graph dbr:Aanderaa dbr:Topological_combinatorics dbr:Subgraph_isomorphism_problem dbr:Evasive_Boolean_function dbr:Richard_M._Karp dbr:Stål_Aanderaa dbr:Jean_Vuillemin dbr:Hereditary_property dbr:Arnold_L._Rosenberg dbr:Aanderaa-Karp-Rosenberg_conjecture dbr:Aanderaa-Rosenberg_conjecture dbr:Aanderaa–Rosenberg_conjecture dbr:Valerie_King dbr:Evasiveness dbr:Evasiveness_conjecture
is dbp:knownFor of	dbr:Richard_M._Karp
is foaf:primaryTopic of	wikipedia-en:Aanderaa–Karp–Rosenberg_conjecture