Copertina

Faster diameter computation in graphs of bounded Euler genus

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kluk, Kacper, Pilipczuk, Marcin, Pilipczuk, Michał, Stamoulis, Giannos
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Minor Containment and Disjoint Paths in almost-linear time
di: Korhonen, Tuukka, et al.
Pubblicazione: (2024)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
di: Chudnovsky, Maria, et al.
Pubblicazione: (2024)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
di: Pilipczuk, Michał, et al.
Pubblicazione: (2025)

Elementary first-order model checking for sparse graphs
di: Gajarský, Jakub, et al.
Pubblicazione: (2024)

Coarse Balanced Separators in Fat-Minor-Free Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Graph classes through the lens of logic
di: Pilipczuk, Michał
Pubblicazione: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
di: Marx, Dániel, et al.
Pubblicazione: (2026)

A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
di: Czyżewska, Jadwiga, et al.
Pubblicazione: (2025)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
di: Kluk, Kacper, et al.
Pubblicazione: (2026)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
di: Kluk, Kacper, et al.
Pubblicazione: (2025)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
di: Bourneuf, Romain, et al.
Pubblicazione: (2025)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
di: Majewski, Konrad, et al.
Pubblicazione: (2022)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2026)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2024)

Variants of Merge-Width and Applications
di: Drabik, Karolina, et al.
Pubblicazione: (2026)

Bounding $\varepsilon$-scatter dimension via metric sparsity
di: Bourneuf, Romain, et al.
Pubblicazione: (2024)

Parameterized Complexity of MinCSP over the Point Algebra
di: Osipov, George, et al.
Pubblicazione: (2023)

Parameterized and approximation algorithms for coverings points with segments in the plane
di: Kowalska, Katarzyna, et al.
Pubblicazione: (2024)

On Integer Programs That Look Like Paths
di: Briański, Marcin, et al.
Pubblicazione: (2025)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Parameterized dynamic data structure for Split Completion
di: Majewski, Konrad, et al.
Pubblicazione: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
di: Jaffke, Lars, et al.
Pubblicazione: (2022)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
di: Majewski, Konrad, et al.
Pubblicazione: (2021)

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

Dynamic Detours
di: Dadush, Daniel, et al.
Pubblicazione: (2026)

Flipper games for monadically stable graph classes
di: Gajarský, Jakub, et al.
Pubblicazione: (2023)

Testing H-freeness on sparse graphs, the case of bounded expansion
di: Humeau, Samuel, et al.
Pubblicazione: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
di: Michel, Lukas, et al.
Pubblicazione: (2024)

Finding the diameter of a tree with distance queries
di: Gerbner, Dániel, et al.
Pubblicazione: (2025)

Making an oriented graph acyclic using inversions of bounded or prescribed size
di: Bang-Jensen, Jørgen, et al.
Pubblicazione: (2025)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
di: Bonamy, Marthe, et al.
Pubblicazione: (2022)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

On coarse tree decompositions and coarse balanced separators
di: Abrishami, Tara, et al.
Pubblicazione: (2025)

A Faster Deterministic Approximation Algorithm for TTP-2
di: Kanaya, Yuga, et al.
Pubblicazione: (2023)

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

Combinatorial Correlation Clustering
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
di: Hatzel, Meike, et al.
Pubblicazione: (2022)

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

Clique-free t-matchings in degree-bounded graphs
di: Paluch, Katarzyna, et al.
Pubblicazione: (2024)