Imagen de Portada

On the non-submodularity of the problem of adding links to minimize the effective graph resistance

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Achterberg, Massimo A., Kooij, Robert E.
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Mathematical Physics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
por: Bengali, Vedangi, et al.
Publicado: (2024)

Enumerating minimal solution sets for metric graph problems
por: Bergougnoux, Benjamin, et al.
Publicado: (2023)

Continuous optimization methods for the graph isomorphism problem
por: Klus, Stefan, et al.
Publicado: (2023)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
por: Castelo, Emanuel, et al.
Publicado: (2025)

Generating minimal redundant and maximal irredundant sets in incidence graphs
por: Castelo, Emanuel, et al.
Publicado: (2026)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
por: Bonamy, Marthe, et al.
Publicado: (2020)

Approximation algorithms for non-sequential star packing problems
por: Hu, Mengyuan, et al.
Publicado: (2024)

Fast approximation algorithms for the 1-median problem on real-world large graphs
por: Ueta, Keisuke, et al.
Publicado: (2025)

Minimizing the effective graph resistance by adding links is NP-hard
por: Kooij, Robert E., et al.
Publicado: (2023)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
por: Arkhipov, Pavel, et al.
Publicado: (2024)

Circular-arc graphs and the Helly property
por: Derbisz, Jan, et al.
Publicado: (2024)

The Complexity of Diameter on H-free graphs
por: Oostveen, Jelle J., et al.
Publicado: (2024)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
por: Ghanbari, Babak, et al.
Publicado: (2025)

Circle graphs can be recognized in linear time
por: Paul, Christophe, et al.
Publicado: (2025)

Packing $K_r$s in bounded degree graphs
por: McKay, Michael, et al.
Publicado: (2022)

Generalizing Roberts' characterization of unit interval graphs
por: Martínez, Virginia Ardévol, et al.
Publicado: (2024)

Reconfiguration of labeled matchings in triangular grid graphs
por: Kakimura, Naonori, et al.
Publicado: (2024)

Independent set reconfiguration in H-free graphs
por: Bartier, Valentin, et al.
Publicado: (2024)

Generation of weighted trees, block trees and block graphs
por: Ekim, Tınaz, et al.
Publicado: (2024)

A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
por: Xiao, Hanyin, et al.
Publicado: (2025)

Max Weight Independent Set in sparse graphs with no long claws
por: Abrishami, Tara, et al.
Publicado: (2023)

A polynomial kernel for vertex deletion into bipartite permutation graphs
por: Derbisz, Jan
Publicado: (2021)

Terminal Steiner tree problem : Complexity and Algorithms
por: S, Jyothish, et al.
Publicado: (2026)

All ascents exponential from valued constraint graphs of pathwidth three
por: Kaznatcheev, Artem, et al.
Publicado: (2026)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
por: Berthe, Gaétan, et al.
Publicado: (2024)

Sequential testing problem: A follow-up review
por: Ünlüyurt, Tonguç
Publicado: (2025)

A column generation algorithm for finding co-3-plexes in chordal graphs
por: Dupont-Bouillard, Alexandre
Publicado: (2026)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
por: Foucaud, Florent, et al.
Publicado: (2025)

Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
por: Liu, Bowie, et al.
Publicado: (2025)

On the number of $k$-mers admitting a given lexicographical minimizer
por: Ingels, Florian, et al.
Publicado: (2024)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
por: Bencs, Ferenc, et al.
Publicado: (2025)

Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
por: Mikulincer, Dan, et al.
Publicado: (2025)

Kawasaki dynamics beyond the uniqueness threshold
por: Bauerschmidt, Roland, et al.
Publicado: (2023)

Fast relaxation of the random field Ising dynamics
por: Alaoui, Ahmed El, et al.
Publicado: (2023)

Pirogov--Sinai Theory Beyond Lattices
por: Cannon, Sarah, et al.
Publicado: (2024)

Perfect Sampling for Hard Spheres from Strong Spatial Mixing
por: Anand, Konrad, et al.
Publicado: (2023)

On boundedness of zeros of the independence polynomial of tori
por: de Boer, David, et al.
Publicado: (2023)

Trickle-Down in Localization Schemes and Applications
por: Anari, Nima, et al.
Publicado: (2024)

On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
por: Blanca, Antonio, et al.
Publicado: (2023)

Cycling in the forest with Wilson's algorithm
por: Fanuel, Michaël, et al.
Publicado: (2024)