Copertina

On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Ameli, Afrouz Jabal, Motiei, Faezeh, Saghafian, Morteza
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Geometry Computational Complexity Combinatorics 05C05, 05C10, 05C12, 05C85, 68Q25 F.2; G.2.1; G.2.2; G.2.3
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the parameterized complexity of computing good edge-labelings
di: de Andrade, Davi, et al.
Pubblicazione: (2024)

Polynomial Bounds for the Graph Minor Structure Theorem
di: Gorsky, Maximilian, et al.
Pubblicazione: (2025)

New results on graph matching from degree preserving growth
di: Erdős, Péter L., et al.
Pubblicazione: (2022)

Optimal Bounds for the k-Disjoint Paths Problem
di: Cavallaro, Dario, et al.
Pubblicazione: (2026)

Quickly excluding an annotated planar graph
di: Gorsky, Maximilian, et al.
Pubblicazione: (2026)

The price of homogeneity is polynomial
di: Gorsky, Maximilian, et al.
Pubblicazione: (2026)

DAG Scheduling in the BSP Model
di: Papp, Pál András, et al.
Pubblicazione: (2023)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
di: Choi, Mujin, et al.
Pubblicazione: (2025)

On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
di: Koutsoutis, Alex, et al.
Pubblicazione: (2025)

The Euclidean MST-ratio for Bi-colored Lattices
di: di Montesano, Sebastiano Cultrera, et al.
Pubblicazione: (2024)

Faster parameterized algorithms for modification problems to minor-closed classes
di: Morelle, Laure, et al.
Pubblicazione: (2022)

Vertex identification to a forest
di: Morelle, Laure, et al.
Pubblicazione: (2024)

Metrics on Permutation Families Defined by a Restriction Graph
di: Tymoshenko, Danylo, et al.
Pubblicazione: (2025)

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes
di: Cunha, Luís Felipe I., et al.
Pubblicazione: (2025)

A New Temporal Interpretation of Cluster Editing
di: Bocci, Cristiano, et al.
Pubblicazione: (2022)

Bipartite Turán problem on cographs
di: Zimmermann, Jakob Paul
Pubblicazione: (2026)

XALP-completeness of Parameterized Problems on Planar Graphs
di: Bodlaender, Hans L., et al.
Pubblicazione: (2024)

On the Diameter of Arrangements of Topological Disks
di: Abiad, Aida, et al.
Pubblicazione: (2025)

Approximating branchwidth on parametric extensions of planarity
di: Thilikos, Dimitrios M., et al.
Pubblicazione: (2023)

Excluding Pinched Spheres
di: Morelle, Laure, et al.
Pubblicazione: (2025)

Killing a Vortex
di: Thilikos, Dimitrios M., et al.
Pubblicazione: (2022)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
di: Krishnaswamy, Ravishankar, et al.
Pubblicazione: (2014)

Independent Locating-Dominating Sets in Pseudotrees
di: Cáceres, José, et al.
Pubblicazione: (2026)

Finding irrelevant vertices in linear time on bounded-genus graphs
di: Golovach, Petr A., et al.
Pubblicazione: (2019)

Identification to Subclasses of Chordal Graphs
di: Golovach, Petr A., et al.
Pubblicazione: (2026)

Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae
di: Dovgal, Sergey, et al.
Pubblicazione: (2023)

On treewidth and maximum cliques
di: Chudnovsky, Maria, et al.
Pubblicazione: (2024)

Graph polynomials: some questions on the edge
di: Farr, Graham, et al.
Pubblicazione: (2024)

On non-planar, cycle-conformal graphs
di: Gorsky, Maximilian, et al.
Pubblicazione: (2026)

How Local Separators Shape Community Structure in Large Networks
di: Frenkel, Sarah, et al.
Pubblicazione: (2025)

On the characterization of graphs with tree 3-spanners
di: Lin, Lan, et al.
Pubblicazione: (2025)

A note on graphs with purely imaginary per-spectrum
di: Singh, Ranveer, et al.
Pubblicazione: (2022)

Asymptotic probability of irreducibles II: sequence
di: Monteil, Thierry, et al.
Pubblicazione: (2025)

A coarse Menger's Theorem for planar and bounded genus graphs
di: Blažej, Václav, et al.
Pubblicazione: (2026)

Catching Rats in $H$-minor-free Graphs
di: Gorsky, Maximilian, et al.
Pubblicazione: (2025)

Dynamic programming on bipartite tree decompositions
di: Jaffke, Lars, et al.
Pubblicazione: (2023)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
di: Morelle, Laure, et al.
Pubblicazione: (2025)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
di: Haslebacher, Sebastian
Pubblicazione: (2025)

Merge Trees of Periodic Filtrations
di: Edelsbrunner, Herbert, et al.
Pubblicazione: (2024)

The Leaf Function of Penrose P2 Graphs
di: Porrier, Carole, et al.
Pubblicazione: (2023)