On interval graphs and matrice profiles

Alain Billionnet

RAIRO - Operations Research - Recherche Opérationnelle (1986)

  • Volume: 20, Issue: 3, page 245-256
  • ISSN: 0399-0559

How to cite

top

Billionnet, Alain. "On interval graphs and matrice profiles." RAIRO - Operations Research - Recherche Opérationnelle 20.3 (1986): 245-256. <http://eudml.org/doc/104904>.

@article{Billionnet1986,
author = {Billionnet, Alain},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {NP-completeness; matrix profile; optimization; interval graph; chronological orderings},
language = {eng},
number = {3},
pages = {245-256},
publisher = {EDP-Sciences},
title = {On interval graphs and matrice profiles},
url = {http://eudml.org/doc/104904},
volume = {20},
year = {1986},
}

TY - JOUR
AU - Billionnet, Alain
TI - On interval graphs and matrice profiles
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1986
PB - EDP-Sciences
VL - 20
IS - 3
SP - 245
EP - 256
LA - eng
KW - NP-completeness; matrix profile; optimization; interval graph; chronological orderings
UR - http://eudml.org/doc/104904
ER -

References

top
  1. [1] J. ABBOTT and M. KATCHALSKI, A Turan type problem for interval graphs, Discrete Mathematics 25, pp. 85-88, 1979. Zbl0391.05033MR522750
  2. [2] G. C. EVERSTINE, A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront, International Journal for numerical methods in engineering, Vol. 14, pp. 837-853, 1979. Zbl0401.73082
  3. [3] D. R. FULKERSON and O. A. GROSS, Incidence matrices and interval graphs, Pacific J. Math., 15, pp. 835-855, 1965. Zbl0132.21001MR186421
  4. [4] M. R. GAREY and D.S. JOHNSON, Comptuers and Intractability, a guide to the theory of NP-Completeness, V. H. Freeman and Company, San Francisco, 1979. Zbl0411.68039MR519066
  5. [5] A. GEORGE and J. W. H. LIU, Computer solutions of large sparse positive definite systems, Prentice Hall, Englewood Cliffs, New Jersey, 324 p., 1981. Zbl0516.65010MR646786
  6. [6] A. GEORGE and J. W. H. LIU, A minimal storage implementation of the minimum degree algorithm, SIAM J. Numer. Anal., Vol. 17, n° 2 April 1980. Zbl0424.65006MR567274
  7. [7] N. E. GIBBS, W. G. POOLE and P. K. STOCKMEYER, An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM J. Numer. Anal., Vol 13, n° 2, April 1976. Zbl0329.65024MR501810
  8. [8] P. C. GILMORE and A. J. HOFFMAN, A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, pp. 539-548, 1964. Zbl0121.26003MR175811
  9. [9] M. C. GOLUMBIC, Algorithmic graph theory and perfect graphs, Academic Press, New York, 284 p., 1980. Zbl0541.05054MR562306
  10. [10] F. ROBERTS, Boxity and cubicity of a graph in Recent Progress in Combinatorics, Tutte ed., Ac. Press, pp. 301-310, 1969. Zbl0193.24301MR252268
  11. [10 bis] D. J. ROSE, Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32, pp. 597-609, 1970. Zbl0216.02602MR270957
  12. [11] D. SKRIENChronological orderings of interval graphs, Discrete Applied Mathematics 8, pp. 69-83, 1984. Zbl0543.05059MR739600
  13. [11 bis] R. E. TARJAN, Graph theory and gaussian elimination in Sparse matrix computations, J. R. Bunch and D. J. Rose, eds, Academic Press, New York, 1976, pp. 3-22. Zbl0347.65017
  14. [12] H. S. WITSENHAUSEN, On intersections of interval graphs, Discrete Mathematics, 31, pp. 211-216, 1980. Zbl0443.05061MR583221
  15. [13] M. YANNAKAKIS, Computing the minimum fill-in is NP-complete, SIAM J. Alg. Disc. Meth., Vol. 2, n° 1, March 1981, pp. 77-79. Zbl0496.68033MR604513

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.