Aanderaa–Karp–Rosenberg conjecture
id:
aanderaa-karp-rosenberg-conjecture-173-2831780
title:
Aanderaa–Karp–Rosenberg conjecture
text:
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex u and vertex v?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg. According to the conjecture, for a wide class of properties, no algorithm can guarantee t
brand slug:
wiki
category slug:
encyclopedia
description:
Unsolved problem on graph query complexity
original url:
https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture
date created:
2009-02-24T01:46:53Z
date modified:
2024-09-02T06:30:11Z
main entity:
{"identifier":"Q4661558","url":"https://www.wikidata.org/entity/Q4661558"}
image:
fields total:
13
integrity:
15