Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs

被引：0
|
作者：
Duraj, Lech [1 ]
Konieczny, Filip [1 ]
Potępa, Krzysztof [1 ]
机构：
[1] Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
来源：
Leibniz International Proceedings in Informatics, LIPIcs | / 308卷
关键词：
Compilation and indexing terms; Copyright 2025 Elsevier Inc;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Computational complexity - Consensus algorithm - Geometry - Graphic methods
引用
收藏
相关论文
共 50 条
  • [1] Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
    Ducoffe, Guillaume
    Habib, Michel
    Viennot, Laurent
    PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), 2020, : 1905 - 1922
  • [2] On the Zarankiewicz Problem for Graphs with Bounded VC-Dimension
    Janzer, Oliver
    Pohoata, Cosmin
    COMBINATORICA, 2024, 44 (04) : 839 - 848
  • [3] Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
    Ducoffe, Guillaume
    Habib, Michel
    Viennot, Laurent
    PROCEEDINGS OF THE 2020 ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2020, : 1905 - 1922
  • [4] Erdős–Hajnal Conjecture for Graphs with Bounded VC-Dimension
    Jacob Fox
    János Pach
    Andrew Suk
    Discrete & Computational Geometry, 2019, 61 : 809 - 829
  • [5] Erds-Hajnal Conjecture for Graphs with Bounded VC-Dimension
    Fox, Jacob
    Pach, Janos
    Suk, Andrew
    DISCRETE & COMPUTATIONAL GEOMETRY, 2019, 61 (04) : 809 - 829
  • [6] ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION
    Mofidi, Alireza
    FACTA UNIVERSITATIS-SERIES MATHEMATICS AND INFORMATICS, 2022, 37 (01): : 121 - 135
  • [7] VC-dimension and pseudo-random graphs
    Pham, Thang
    Senger, Steven
    Tait, Michael
    Thu-Huyen, Nguyen
    DISCRETE APPLIED MATHEMATICS, 2025, 365 : 231 - 246
  • [8] The VC-dimension of set systems defined by graphs
    Carleton University, School of Computer Science, Ottawa, Ont. K1S 5B6, Canada
    不详
    不详
    不详
    Discrete Appl Math, 3 (237-257):
  • [9] The VC-dimension of set systems defined by graphs
    Kranakis, E
    Krizanc, D
    Ruf, B
    Urrutia, J
    Woeginger, G
    DISCRETE APPLIED MATHEMATICS, 1997, 77 (03) : 237 - 257
  • [10] IDENTIFYING CODES IN HEREDITARY CLASSES OF GRAPHS AND VC-DIMENSION
    Bousquet, Nicolas
    Lagoutte, Aurelie
    Li, Zhentao
    Parreau, Aline
    Thomasse, Stephan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (04) : 2047 - 2064
12345