SIAM Journal on Applied Mathematics · 1978 · 296 citations · 21 references
ComputingComputer ScienceAlgorithmsCombinatoricsTheory Of ComputationAlgorithm AnalysisComputational ComplexityDirected Acyclic GraphsGraph AlgorithmsGraph TheoryMatrix ComputationAdjacency MatricesAlgorithmic Graph TheoryComplexityComputational Complexity Of Graph AlgorithmsPermutationsSparse Linear AlgebraSparse Matrix AlgorithmsSparse Matrix Computation
A linear-time algorithm for sparse symmetric matrices which converts a matrix into pentadiagonal form (bandwidth 2), whenever it is possible to do so using simultaneous row and column permutations is described.
21
The Complexity of Flowshop and Jobshop Scheduling
M. R. Garey, David Johnson, Ravi Sethi · Mathematics of Operations Research · 1976 · 2.6K citations
Some simplified NP-complete graph problems
M. R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science · 1976 · 2.1K citations
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text
`` Strong '' NP-Completeness Results
M. R. Garey, David Johnson · Journal of the ACM · 1978 · 657 citations · Full text