**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# An algorithm for source location in directed graphs

Abstract

A polynomial time solution algorithm is described to find a smallest subset R of nodes of a directed graph D=(V,A) such that, for every node v in V-R, there are k edge-disjoint paths from R to v and there are l edge-disjoint paths from v to R.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (6)

Edge disjoint shortest pair algorithm

Edge disjoint shortest pair algorithm is an algorithm in computer network routing. The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices. For an undirected graph G(V, E), it is stated as follows: Run the shortest path algorithm for the given pair of vertices Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex Make the length of each of the above arcs negative Run the shortest path algorithm (Note: the algorithm should accept negative costs) Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now.

Acoustic location

Acoustic location is the use of sound to determine the distance and direction of its source or reflector. Location can be done actively or passively, and can take place in gases (such as the atmosphere), liquids (such as water), and in solids (such as in the earth). Active acoustic location involves the creation of sound in order to produce an echo, which is then analyzed to determine the location of the object in question.

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.