Abstrakt. Vi presenterar en linjär tid algoritm för sparse symmetriska matriser som omvandlar en matris till pentadiagonal form ("bandbredd 2"), när det är möjligt att göra det med hjälp av samtidig rad och kolumn permutationer. Å andra sidan när ett godtyckligt heltal k och graf G ges, visar vi att det är NP-komplett att avgöra om det finns en beställning av hörnen så att adjacensmatrisen har bandbredd - < k, även när G återställs till klassen av fria träd med alla hörn av grad - < 3. Relaterade problem för acykliska riktade grafer (övre triangulära matriser) diskuteras också.
Det visas att problemet är NP-komplett även för träd av maximal grad 3 REF.
COMPLEXITY RESULTS FOR BANDWIDTH MINIMIZATION
{'venue': None, 'journal': 'Siam Journal on Applied Mathematics', 'mag_field_of_study': ['Mathematics']}