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

DOI10.1016/J.IPL.2009.06.011MaRDI QIDQ989571zbMATH OpenOpenAlexFDO

Authors B. S. Panda, Sajal K. Das

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

graph algorithmschordal graphsparallel algorithmsproper interval graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1955841
• A linear time recognition algorithm for proper interval graphs
• scientific article; zbMATH DE number 3892606
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• scientific article; zbMATH DE number 123468

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1955841 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• A linear time recognition algorithm for proper interval graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Efficient Parallel Algorithms for Chordal Graphs
• Finding Hamiltonian circuits in proper interval graphs
• Incidence matrices and interval graphs
• Intersection graphs of paths in a tree
• New sequential and parallel algorithms for interval graph recognition
• On the Desirability of Acyclic Database Schemes
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Parallel Merge Sort
• Polynomially bounded algorithms for locatingp-centers on a tree
• Representations of chordal graphs as subtrees of a tree
• Scheduling Interval-Ordered Tasks
• Some parallel algorithms on interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(5)

• Block-indifference graphs: characterization, structural and spectral properties
• scientific article; zbMATH DE number 1955841 (Why is no real title available?)
• Non-inclusion and other subclasses of chordal graphs
• Semi-proper interval graphs
• Counting and enumerating unlabeled split-indifference graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989571)