A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph | PERPUSTAKAAN UNIVERSITAS KATOLIK PARAHYANGAN

Pencarian berdasarkan :

Pencarian terakhir:

Text

A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph

Guo, Yongyan - Nama Orang; Wu, Gang - Nama Orang;

Separator minimization is an important problem in graph partitioning. Although finding an optimum partitioning for a given graph is NP-hard, estimating the size of the smallest vertex separator is an interesting problem since it can be used to assess the quality of a vertex separator. In [A. Pothen, H. Simon, and K. Liou, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 430--452], two classical lower bounds on the size of the smallest vertex separator of a graph were established. In the present work, we revisit this problem and establish a new and easily computable lower bound on the smallest vertex separator.

Ketersediaan

Barcode		Tipe Koleksi	Nomor Panggil	Lokasi	Status
art141550	null	Artikel		Gdg9-Lt3	Tersedia namun tidak untuk dipinjamkan - No Loan

Informasi Detail

Judul Seri: SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS; Vol.43 No.1 January-March 2022
No. Panggil: -
Penerbit: : .,
Deskripsi Fisik: p. 370-376
Bahasa: English
ISBN/ISSN: -
Klasifikasi: NONE
Tipe Isi: -
Tipe Media: -
Tipe Pembawa: -
Edisi: -
Subjek: GRAPH PARTITIONING
SPECTRAL METHOD
LAPLACIAN MATRIX
VERTEX SEPARATOR
SEPARATOR MINIMIZATION
Info Detail Spesifik: https://doi.org/10.1137/20M1382118
Pernyataan Tanggungjawab: Yongyan Guo, Gang Wu

Versi lain/terkait

Tidak tersedia versi lain

Lampiran Berkas

Tidak Ada Data

Komentar

Anda harus masuk sebelum memberikan komentar