Publication

A route pre-computation algorithm for integrated services networks

Jean-Yves Le Boudec
1995
Journal Articles

Abstract

We provide an algorithm for computing best paths on a graph where edges have a multidimensional cost, one dimension representing delay, the others representing available capacity. Best paths are those which guarantee maximum capacity with least possible delay. The complexity of the algorithm is of the order of O(V3) in the bidimensional case, for a graph withV vertices. The results can be used for routing connections with guaranteed capacity in a communication network.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Jean-Yves Le Boudec
1995
Journal Articles

Abstract

Official source

Related concepts (32)

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Related publications (31)

A route pre-computation algorithm for integrated services networks

Chat with Graph Search

AFEC: A knowledge graph capturing social intelligence in casual conversations

Dataset: Modelling human activities in a system of cities

Tackling Hardness using Spin Glass Physics: from Inference to Sampling through Diffusions