Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/41035
Registo completo
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.author | Andrade, Enide | pt_PT |
dc.contributor.author | Dahl, Geir | pt_PT |
dc.date.accessioned | 2024-03-12T10:45:20Z | - |
dc.date.available | 2024-03-12T10:45:20Z | - |
dc.date.issued | 2024-04-15 | - |
dc.identifier.issn | 0024-3795 | pt_PT |
dc.identifier.uri | http://hdl.handle.net/10773/41035 | - |
dc.description.abstract | Partition problems in graphs are extremely important in applications, as shown in the Data Science and Machine Learning literature. One approach is spectral partitioning based on a Fiedler vector, i.e., an eigenvector corresponding to the second smallest eigenvalue $a(G)$ of the Laplacian matrix $L_G$ of the graph $G$. This problem corresponds to the minimization of a quadratic form associated with $L_G$, under certain constraints involving the $\ell_2$-norm. We introduce and investigate a similar problem, but using the $\ell_1$-norm to measure distances. This leads to a new parameter $b(G)$ as the optimal value. We show that a well-known cut problem arises in this approach, namely the sparsest cut problem. We prove connectivity results and different bounds on this new parameter, relate to Fiedler theory and show explicit expressions for $b(G)$ for trees. We also comment on an $\ell_{\infty}$-norm version of the problem. | pt_PT |
dc.description.sponsorship | Portuguese funds through the CIDMA - Center for Research and Development in Mathematics and Applications, and the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia) | pt_PT |
dc.language.iso | eng | pt_PT |
dc.publisher | Elsevier | pt_PT |
dc.relation | info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F04106%2F2020/PT | pt_PT |
dc.relation | info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDP%2F04106%2F2020/PT | pt_PT |
dc.rights | openAccess | pt_PT |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | pt_PT |
dc.subject | Algebraic connectivity | pt_PT |
dc.subject | Graph partition | pt_PT |
dc.subject | Sparsest cut | pt_PT |
dc.subject | L1-norm | pt_PT |
dc.title | Combinatorial Fiedler theory and graph partition | pt_PT |
dc.type | article | pt_PT |
dc.description.version | published | pt_PT |
dc.peerreviewed | yes | pt_PT |
degois.publication.firstPage | 229 | pt_PT |
degois.publication.lastPage | 251 | pt_PT |
degois.publication.title | Linear Algebra and its Applications | pt_PT |
degois.publication.volume | 687 | pt_PT |
dc.relation.publisherversion | https://doi.org/10.1016/j.laa.2024.02.005 | pt_PT |
dc.identifier.doi | 10.1016/j.laa.2024.02.005 | pt_PT |
dc.identifier.essn | 1873-1856 | pt_PT |
Aparece nas coleções: | CIDMA - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
EAGDfile.pdf | 534.51 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.