Cover Image

Practical Computation of Graph VC-Dimension

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Coudert, David, Csikós, Mónika, Ducoffe, Guillaume, Viennot, Laurent
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
by: Csikós, Mónika, et al.
Published: (2023)

Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
by: Dragan, Feodor F., et al.
Published: (2018)

Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
by: Aubian, Guillaume, et al.
Published: (2025)

Bow Metrics and Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
by: Ducoffe, Guillaume
Published: (2026)

Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics
by: Cauvi, Justine, et al.
Published: (2025)

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Quasilinear-time eccentricities computation, and more, on median graphs
by: Bergé, Pierre, et al.
Published: (2024)

Parameterized Restless Temporal Path
by: Cauvi, Justine, et al.
Published: (2025)

Making Temporal Betweenness Computation Faster and Restless
by: Brunelli, Filippo, et al.
Published: (2025)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
by: Dahan, Anatole, et al.
Published: (2026)

On $G^p$-unimodality of radius functions in graphs: structure and algorithms
by: Chalopin, Jérémie, et al.
Published: (2025)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

Efficient Contractions of Dynamic Graphs -- with Applications
by: Henzinger, Monika, et al.
Published: (2025)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Computing k-mers in Graphs
by: Alanko, Jarno N., et al.
Published: (2025)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

Diameter Computation on (Random) Geometric Graphs
by: Bläsius, Thomas, et al.
Published: (2026)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Computing the Center of Uncertain Points on Cactus Graphs
by: Hu, Ran, et al.
Published: (2024)

Computing the LCP Array of a Labeled Graph
by: Alanko, Jarno, et al.
Published: (2024)

Improved Algorithms for Effective Resistance Computation on Graphs
by: Yang, Yichun, et al.
Published: (2025)

Online Matching in Geometric Random Graphs
by: Sentenac, Flore, et al.
Published: (2023)

Kernelization for Orthogonality Dimension
by: Haviv, Ishay, et al.
Published: (2024)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
by: Chalermsook, Parinya, et al.
Published: (2025)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
by: Li, Yi, et al.
Published: (2022)

Convolution and Knapsack in Higher Dimensions
by: Grage, Kilian, et al.
Published: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems
by: Stout, Quentin F.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Maximizing the Minimum Eigenvalue in Constant Dimension
by: Brown, Adam, et al.
Published: (2024)

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

Improved Lower Bounds for Privacy under Continual Release
by: Aryanfard, Bardiya, et al.
Published: (2025)

Improved Differentially Private Continual Observation Using Group Algebra
by: Henzinger, Monika, et al.
Published: (2024)