EUVIMEDEUVIMED entdecken
Crossref

Evasiveness of Graph Properties and Topological Fixed-Point Theorems

Carl A. Miller

Foundations and Trends® in Theoretical Computer Science · 2013

DOI: 10.1561/0400000055 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, 2013. Verfasst von Carl A. Miller. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 42 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 the early 1970s that all monotone graph properties are evasive—that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.

Zitieren

APA

Miller, C. A. (2013). Evasiveness of Graph Properties and Topological Fixed-Point Theorems. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000055

Vancouver

Miller CA. Evasiveness of Graph Properties and Topological Fixed-Point Theorems. Foundations and Trends® in Theoretical Computer Science. 2013. doi:10.1561/0400000055

BibTeX
@article{Miller2013,
  author = {Miller, Carl A.},
  title = {Evasiveness of Graph Properties and Topological Fixed-Point Theorems},
  journal = {Foundations and Trends® in Theoretical Computer Science},
  year = {2013},
  doi = {10.1561/0400000055}
}
Kostenlos starten →