Triangle-Saturated Graphs in the Semi-Random Graph Process
The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the algorithm independently and uniformly at random. The algorithm then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. We also consider the offline version of the process in which the algorithm is given the entire sequence of random vertex choices before the selection takes place. For a given graph property, the objective of the algorithm is to force the graph to satisfy this…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.14687
curl -X POST /api/v1/records/arxiv/2608.14687/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.14687/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'