Buchumschlag

Fast approximation algorithms for the 1-median problem on real-world large graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ueta, Keisuke, Wu, Wei, Yagiura, Mutsunori
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)

Approximation algorithms for non-sequential star packing problems
von: Hu, Mengyuan, et al.
Veröffentlicht: (2024)

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

Continuous optimization methods for the graph isomorphism problem
von: Klus, Stefan, et al.
Veröffentlicht: (2023)

A column generation algorithm for finding co-3-plexes in chordal graphs
von: Dupont-Bouillard, Alexandre
Veröffentlicht: (2026)

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

Parameterised algorithms for temporally satisfying reconfiguration problems
von: Davot, Tom, et al.
Veröffentlicht: (2025)

Aggregating maximal cliques in real-world graphs
von: Alon, Noga, et al.
Veröffentlicht: (2025)

Holey graphs: very large Betti numbers are testable
von: Szabó, Dániel, et al.
Veröffentlicht: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
von: Deák, Bence, et al.
Veröffentlicht: (2026)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
von: Alecu, Bogdan, et al.
Veröffentlicht: (2024)

Enumerating minimal solution sets for metric graph problems
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2023)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

Circular-arc graphs and the Helly property
von: Derbisz, Jan, et al.
Veröffentlicht: (2024)

The Complexity of Diameter on H-free graphs
von: Oostveen, Jelle J., et al.
Veröffentlicht: (2024)

A 4-approximation algorithm for min max correlation clustering
von: Heidrich, Holger, et al.
Veröffentlicht: (2023)

Fast Makespan Minimization via Short ILPs
von: Hermelin, Danny, et al.
Veröffentlicht: (2026)

Circle graphs can be recognized in linear time
von: Paul, Christophe, et al.
Veröffentlicht: (2025)

Packing $K_r$s in bounded degree graphs
von: McKay, Michael, et al.
Veröffentlicht: (2022)

Generalizing Roberts' characterization of unit interval graphs
von: Martínez, Virginia Ardévol, et al.
Veröffentlicht: (2024)

Reconfiguration of labeled matchings in triangular grid graphs
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

Independent set reconfiguration in H-free graphs
von: Bartier, Valentin, et al.
Veröffentlicht: (2024)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
von: Tan, Jingjing
Veröffentlicht: (2024)

Solving the List Coloring Problem through a Branch-and-Price algorithm
von: Lucci, Mauro, et al.
Veröffentlicht: (2023)

Generation of weighted trees, block trees and block graphs
von: Ekim, Tınaz, et al.
Veröffentlicht: (2024)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

Max Weight Independent Set in sparse graphs with no long claws
von: Abrishami, Tara, et al.
Veröffentlicht: (2023)

A polynomial kernel for vertex deletion into bipartite permutation graphs
von: Derbisz, Jan
Veröffentlicht: (2021)

Terminal Steiner tree problem : Complexity and Algorithms
von: S, Jyothish, et al.
Veröffentlicht: (2026)

All ascents exponential from valued constraint graphs of pathwidth three
von: Kaznatcheev, Artem, et al.
Veröffentlicht: (2026)

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

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
von: Jordon, Addie, et al.
Veröffentlicht: (2025)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
von: Xiao, Chenglong, et al.
Veröffentlicht: (2024)

Sequential testing problem: A follow-up review
von: Ünlüyurt, Tonguç
Veröffentlicht: (2025)

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

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

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2024)

A logarithmic approximation of linearly ordered colourings
von: Håstad, Johan, et al.
Veröffentlicht: (2024)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)