Buchumschlag

The Complexity of Diameter on H-free graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Oostveen, Jelle J., Paulusma, Daniël, van Leeuwen, Erik Jan
Format:	Preprint
Veröffentlicht:	2024
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

Parameterized Complexity of Streaming Diameter and Connectivity Problems
von: Oostveen, Jelle J., et al.
Veröffentlicht: (2022)

Computing Subset Vertex Covers in $H$-Free Graphs
von: Brettell, Nick, et al.
Veröffentlicht: (2023)

Colouring Probe $H$-Free Graphs
von: Paulusma, Daniël, et al.
Veröffentlicht: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
von: Johnson, Matthew, et al.
Veröffentlicht: (2022)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
von: Lucke, Felicia, et al.
Veröffentlicht: (2023)

Bounding Width on Graph Classes of Constant Diameter
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2025)

Steiner Forest for $H$-Subgraph-Free Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
von: Lucke, Felicia, et al.
Veröffentlicht: (2024)

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

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
von: Gaikwad, Ajinkya
Veröffentlicht: (2025)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2025)

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

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

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
von: Le, Hoang-Oanh, et al.
Veröffentlicht: (2024)

Finding $d$-Cuts in Probe $H$-Free Graphs
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2025)

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

Clique-free t-matchings in degree-bounded graphs
von: Paluch, Katarzyna, et al.
Veröffentlicht: (2024)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
von: Ahn, Jungho, 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)

Interval H-graphs : Recognition and forbidden obstructions
von: Müller, Haiko, et al.
Veröffentlicht: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
von: Marx, Dániel, et al.
Veröffentlicht: (2026)

Solving Problems on Generalized Convex Graphs via Mim-Width
von: Bonomo-Braberman, Flavia, et al.
Veröffentlicht: (2020)

Triangle-free 2-matchings
von: Paluch, Katarzyna
Veröffentlicht: (2023)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
von: Galby, Esther, et al.
Veröffentlicht: (2025)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
von: de Montgolfier, Fabien, et al.
Veröffentlicht: (2025)

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)

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

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)

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

Nearly Tight Bounds on Testing of Metric Properties
von: Bao, Yiqiao, et al.
Veröffentlicht: (2024)

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

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

Parameterized Complexity of Path Set Packing
von: Aravind, N. R., et al.
Veröffentlicht: (2022)

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

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

Parameterized Complexity of Submodular Minimization under Uncertainty
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

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

Reconfiguration of List Colourings
von: Cambie, Stijn, et al.
Veröffentlicht: (2025)