A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs

DOI10.1016/j.ipl.2009.06.011zbMath1202.68478OpenAlexW1993343925MaRDI QIDQ989571

Sajal K. Das, B. S. Panda

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.06.011

zbMATH Keywords

parallel algorithmsgraph algorithmschordal graphsproper interval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Counting and enumerating unlabeled split–indifference graphs ⋮ Non-inclusion and other subclasses of chordal graphs ⋮ Block-indifference graphs: characterization, structural and spectral properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New sequential and parallel algorithms for interval graph recognition
• A linear time recognition algorithm for proper interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Intersection graphs of paths in a tree
• Some parallel algorithms on interval graphs
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• A characterisation of rigid circuit graphs
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On the Desirability of Acyclic Database Schemes
• Parallel Merge Sort
• Scheduling Interval-Ordered Tasks
• Representations of chordal graphs as subtrees of a tree
• Polynomially bounded algorithms for locatingp-centers on a tree
• Efficient Parallel Algorithms for Chordal Graphs

This page was built for publication: A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs