Let G= (V,E) be a finite undirected graph with four distinguished vertices s, t, u, v. The two path problem (TPP) is to determine whether there exist two vertex disjoint paths connecting s with t and u with v and to find such paths if they exist. In this paper, a simple and efficient algorithm for TPP restricted to 2-connected chordal graphs is given. The reduction of TPP for a general chordal graph to the TPP for a 2-connected chordal graph is outlined. © 1988, Springer-Verlag.

Swaminathan V. Krishnan

Chandrasekharan Pandu Rangan

S. Seshadri

Software engineering

CHORDAL GRAPHS

LINEAR ALGORITHMS

SIMPLE AND EFFICIENT ALGORITHMS

TWO PATHS

Undirected graph

VERTEX DISJOINT PATHS

Graph theory

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

A New Linear Algorithm for the Two Path Problem on Chordal Graphs

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

An efficient reduction process for path problems on circular-arc graphs is introduced. For the parity path problem, this reduction gives an O(n+m) algorithm for proper circular-arc graphs, and an O(n+m) algorithm for general circular-arc graphs. This reduction also gives an O(n+m) algorithm for the two path problem on circular-arc graphs. © 1991 BIT Foundations.

Efficient reduction for path problems on circular-arc graphs

Linear algorithms for parity path and two path problems on circular-arc graph

A new linear algorithm for the two path problem on chordal graphs

Journal	Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Data powered by TypesetSpringer Verlag
ISSN	03029743
Open Access	No