Optimal Scheduling of Parallel Tasks with Known Dependencies

This is maybe a trivial question, but I am stuck with the problem.

Suppose we have a general graph:

$$G=(V,E)$$

Each edge represents a task, each vertex represents a data for the task (hence each task works with two vertices).

When two tasks with common vertex run in parallel, some computation time is lost because two tasks cannot use the same vertex at the same time (one have to wait).

I am thinking about the following approaches:

• Create a table of locks telling whether the vertex is free to use or locked. The run all tasks and each taks will wait until the required data are free (maybe setting priority of the waiting tasks to low would suffice).
• Pick maximum number of edges that have no common vertices (better way then greedy algorithm?) and then run all corresponding tasks without locking. Repeat until there are remaining edges.

I am not sure which approach is more efficient. Any ideas/insights? I am totally new to parallel programming...