Keyword: Chordless Path : Search

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

Advanced Search

SEARCH GUIDE

Results: 1 - 1of1

Follow results:

per page:

Sort: Relevance

Context for search term 1Search term 1*

All Dates

LastSelect static range

Custom Range

Select starting monthSelect starting year

Select ending monthSelect ending year

Search name	Searched On	Run search
Keyword: Function Field (10)	23 Mar 2025	Run
Keyword: Chordless Path (1)	23 Mar 2025	Run
Keyword: Rational Links (6)	23 Mar 2025	Run
Keyword: Index Profiles (1)	23 Mar 2025	Run
Keyword: 2-bridge Links (6)	23 Mar 2025	Run

articleNo Access
Parallel Algorithms for Recognizing P₅-free and -free Weakly Chordal Graphs
- Stavros D. Nikolopoulos and
- Leonidas Palios
Parallel Processing Letters01 Mar 2004
Preview Abstract
We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P₅-free and -free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O(log²n) time and require O(m²/log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P₅s and in weakly chordal graphs in O(log n) time with O(m²/logn) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate for the existence of a P₅ (or a ) in case the input graph is not P₅-free (respectively, -free) weakly chordal.

1