Recognizing and representing proper interval graphs in parallel using merging and sorting
From MaRDI portal
Publication:869564
DOI10.1016/j.dam.2006.07.005zbMath1109.68079OpenAlexW2108225866MaRDI QIDQ869564
Louis Ibarra, Jing Huang, Jörgen Bang-Jensen
Publication date: 8 March 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.005
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (4)
Integer merging on EREW PRAM ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Parallel merging with restriction
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple linear time recognition of unit interval graphs
- Interval graphs and related topics
- Efficient parallel recognition of some circular arc graphs. I
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On testing consecutive-ones property in parallel
- Parallel algorithms for maximum matching in complements of interval graphs and related problems
- Optimal greedy algorithms for indifference graphs
- Betweenness, orders and interval graphs
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- The NP-completeness column: an ongoing guide
- Finding Triconnected Components by Local Replacement
- Topics in Intersection Graph Theory
- Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs
- A Parallel Algorithm for Computing Minimum Spanning Trees
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Efficient Parallel Algorithms for Chordal Graphs
This page was built for publication: Recognizing and representing proper interval graphs in parallel using merging and sorting
