About: Node Disjoint Paths (NDP) is one of the extensively studied Graph Theory problem. In this problem, the input is a directed n vertex graph and the set of source destination pair of vertices. The goal is to find the maximum number of paths connecting each such pair, so that such discovered paths are node-disjoint. In this paper, a novel Canine Inspired Algorithm is proposed which is a bio-inspired one, based on the olfactory capabilities of canines in tracing and reaching a destination. Currently many of the existing algorithms try to identify disjoint paths in a linear manner, whereas the Canine algorithm can be executed in a concurrent manner, depending on the number of canines deployed to find the disjoint paths. The time complexity of the algorithm is estimated to be [Formula: see text] . We hope that this algorithm finds many applications in problems related to various fields such as communication networks, scheduling and transportation and provides better results.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

AttributesValues
type
value
  • Node Disjoint Paths (NDP) is one of the extensively studied Graph Theory problem. In this problem, the input is a directed n vertex graph and the set of source destination pair of vertices. The goal is to find the maximum number of paths connecting each such pair, so that such discovered paths are node-disjoint. In this paper, a novel Canine Inspired Algorithm is proposed which is a bio-inspired one, based on the olfactory capabilities of canines in tracing and reaching a destination. Currently many of the existing algorithms try to identify disjoint paths in a linear manner, whereas the Canine algorithm can be executed in a concurrent manner, depending on the number of canines deployed to find the disjoint paths. The time complexity of the algorithm is estimated to be [Formula: see text] . We hope that this algorithm finds many applications in problems related to various fields such as communication networks, scheduling and transportation and provides better results.
Subject
  • Algorithms
  • Graph theory
  • Biological engineering
  • Mathematical logic
  • Theoretical computer science
  • Basic concepts in set theory
  • Asymptotic analysis
  • Analysis of algorithms
  • Set families
  • Bioinspiration
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software