Question

For a system of tasks that may lock resources, the “wait-for” one of these constructs can be used to represent the system state and identify deadlocks. Weisfeiler-Leman algorithms are used on these objects, which may be used to construct a static schedule by building one of these objects. In 2015, László Babai announced work on a problem named for these objects that runs in quasipolynomial (15[1])time. The expression D minus A gives a type of (*) Laplacian representing these objects. One of these objects that obeys the triangle inequality is used as input for the Christofides algorithm. Kruskal’s algorithm constructs a minimum spanning tree on these (10[1])objects, which may be used for causality diagramming in their directed acyclic (10[1])form. For 10 points, name these objects that consist of a collection of vertices connected by edges. ■END■

ANSWER: graphs [accept directed graphs; accept directed acyclic graphs; accept graph Laplacian; accept graph isomorphism problem; accept wait-for graph; accept DAGs; prompt on isomorphisms by asking “what other objects name that problem?;” reject trees]
<RA, Other Science: Computer Science>
= Average correct buzz position

Back to tossups

Buzzes

PlayerTeamOpponentBuzz PositionValue
Mattias EhatammWaterlooOttawa C6415
Sky LiToronto Ray Of Sun In The SkyOttawa A10410
Ian ChowMcDouble West CarletonOttawa B11610

Summary

2023 ARCADIA at UC BerkeleyPremiereY2100%50%50%83.00
2023 ARCADIA at Carleton UniversityPremiereY3100%33%0%94.67
2023 ARCADIA at Claremont CollegesPremiereY1100%100%0%60.00
2023 ARCADIA at IndianaPremiereY580%20%40%104.75
2023 ARCADIA at RITPremiereY2100%50%50%80.00
2023 ARCADIA at WUSTLPremiereY3100%0%0%120.67