The increasing market penetration of connected vehicles supports the development of highly automated vehicles for various traffic situations. Especially intersections form a bottleneck for the traffic flow and thus offer a high potential not only to increase the efficiency, but also to ensure safety. This paper presents a decoupled and decentralized approach using graph-based methods to optimize longitudinal trajectories for multiple vehicles at urban intersections. The approach enables the vehicles to cooperate, while avoiding collisions, considering dynamic influences like traffic lights, and minimizing a cost function. Furthermore, several heuristics are introduced, reducing the computational effort to solve these complex tasks. Simulations of an intersection scenario using the Monte Carlo method show a reduction of summarized costs, which represent travel time, efficiency and driving comfort, by ~28% compared to a driver model and by ~2.6% compared to a non-cooperative system.