All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 14 Next

Displaying 261 – 280 of 1226

Showing per page

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r , s -graphic

Jian Hua Yin (2012)

Czechoslovak Mathematical Journal

The split graph K r + K s ¯ on r + s vertices is denoted by S r , s . A non-increasing sequence π = ( d 1 , d 2 , ... , d n ) of nonnegative integers is said to be potentially S r , s -graphic if there exists a realization of π containing S r , s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S r , s -graphic. They are extensions of two theorems due to A. R. Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series...

A linear algorithm for the two paths problem on permutation graphs

C.P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, Minko, Ionut Andreica, Mugurel, Manev, Krassimir, Tapus, Nicolae (2012)

Serdica Journal of Computing

ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...

Currently displaying 261 – 280 of 1226