Recognizing and representing proper interval graphs in parallel using merging and sorting
From MaRDI portal
Publication:869564
DOI10.1016/J.DAM.2006.07.005zbMATH Open1109.68079OpenAlexW2108225866MaRDI QIDQ869564FDOQ869564
Authors: Jing Huang, Louis Ibarra, 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
Recommendations
- scientific article; zbMATH DE number 123468
- Parallel computation on interval graphs: algorithms and experiments
- Some parallel algorithms on interval graphs
- scientific article; zbMATH DE number 3892606
- Parallel algorithms on interval graphs
- Designing efficient parallel algorithms on interval graphs
- A linear-time algorithm for proper interval graph recognition
- A linear time recognition algorithm for proper interval graphs
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Cites Work
- Topics in Intersection Graph Theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Optimal greedy algorithms for indifference graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Title not available (Why is that?)
- Simple linear time recognition of unit interval graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Parallel Algorithm for Computing Minimum Spanning Trees
- The NP-completeness column: an ongoing guide
- Efficient parallel recognition of some circular arc graphs. I
- On testing consecutive-ones property in parallel
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- Betweenness, orders and interval graphs
- Efficient Parallel Algorithms for Chordal Graphs
- Interval graphs and related topics
- Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs
- Parallel algorithms for maximum matching in complements of interval graphs and related problems
- Finding Triconnected Components by Local Replacement
Cited In (5)
- A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs
- Parallel merging with restriction
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- Integer merging on EREW PRAM
- New sequential and parallel algorithms for interval graph recognition
This page was built for publication: Recognizing and representing proper interval graphs in parallel using merging and sorting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q869564)
