, Any other operation corresponds to an edge of the spanning path that is stabbed by a hyperedge of H ,G (? r ), and as a result there can only beÕ
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs, SODA, pp.377-391, 2016. ,
A separator theorem for nonplanar graphs, Journal of the American Mathematical Society, vol.3, issue.4, pp.801-808, 1990. ,
The Vapnik-Chervonenkis dimension of a random graph, Discrete Mathematics, vol.138, issue.1-3, pp.43-56, 1995. ,
Towards tight approximation bounds for graph diameter and eccentricities, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp.267-280, 2018. ,
Graphs and hypergraphs, 1973. ,
On the crossing spanning tree problem, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.51-60, 2004. ,
, Graph theory, 2008.
Into the square: On the complexity of some quadratictime solvable problems, Electronic Notes in Theoretical Computer Science, vol.322, pp.51-67, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01390131
Identifying codes in hereditary classes of graphs and VC-dimension, SIAM Journal on Discrete Mathematics, vol.29, issue.4, pp.2047-2064, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01038012
VC-dimension and Erd?s-Pósa property, Discrete Mathematics, vol.338, issue.12, pp.2302-2317, 2015. ,
The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Applied Mathematics, vol.82, issue.1-3, pp.43-77, 1998. ,
Dually chordal graphs, SIAM Journal on Discrete Mathematics, vol.11, issue.3, pp.437-455, 1998. ,
Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth, In IPEC, 2018. ,
Product range spaces, sensitive sampling, and derandomization, SIAM J. Comput, vol.28, issue.5, pp.1552-1575, 1999. ,
Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs, ACM Transactions on Algorithms (TALG), vol.15, issue.2, p.21, 2018. ,
New bounds for approximating extremal distances in undirected graphs, Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA 2016), pp.363-376, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01526665
Optimal partition trees, Discrete & Computational Geometry, vol.47, issue.4, pp.661-690, 2012. ,
Quasi-optimal range searching in spaces of finite VC-dimension. Discrete & Computational Geometry, vol.4, pp.467-489, 1989. ,
Better approximation algorithms for the graph diameter, Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp.1041-1052, 2014. ,
Covering planar graphs with a fixed number of balls, Discrete & Computational Geometry, vol.37, issue.2, pp.237-244, 2007. ,
Solving linear programs in the current matrix multiplication time, STOC, pp.938-942, 2019. ,
Diameter determination on restricted graph families, Discrete Applied Mathematics, vol.113, issue.2-3, pp.143-166, 2001. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00090363
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs, SODA'18, pp.2765-2784, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01676187
On the hardness of partially dynamic graph problems and connections to diameter, 43rd International Colloquium on Automata, Languages, and Programming, vol.48, pp.1-48, 2016. ,
Computing giant graph diameters, IWOCA, pp.373-384, 2016. ,
Parameterized learning complexity, COLT, pp.51-57, 1993. ,
A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters, 2nd Symposium on Simplicity in Algorithms, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-01974190
Fast diameter computation within split graphs ,
URL : https://hal.archives-ouvertes.fr/hal-02307397
On classes of graphs with strongly sublinear separators, European Journal of Combinatorics, vol.71, pp.1-11, 2018. ,
Strongly sublinear separators and polynomial expansion, SIAM Journal on Discrete Mathematics, vol.30, issue.2, pp.1095-1101, 2016. ,
Treewidth of graphs with balanced separations, Journal of Combinatorial Theory, Series B, vol.137, pp.137-144, 2019. ,
The VC dimension of k-fold union, Information Processing Letters, vol.101, issue.5, pp.181-184, 2007. ,
Diameter and treewidth in minor-closed graph families, Algorithmica, vol.27, issue.3-4, pp.275-291, 2000. ,
Dynamic generators of topologically embedded graphs, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.599-608, 2003. ,
Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs, 2016. ,
Computation of the center and diameter of outerplanar graphs, Discrete Applied Mathematics, vol.2, issue.3, pp.185-191, 1980. ,
Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, vol.16, issue.6, pp.1004-1022, 1987. ,
Voronoi diagrams on planar graphs, and computing the diameter in deterministicÕ(n 5/3 ) time, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp.495-514, 2018. ,
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, vol.234, issue.1-2, pp.59-84, 2000. ,
Approximating Spanning Trees with Low Crossing Number, 2009. ,
Approximation algorithms for polynomial-expansion and lowdensity graphs, SIAM Journal on Computing, vol.46, issue.6, pp.1712-1744, 2017. ,
, ?-nets and simplex range queries. Discrete & Computational Geometry, vol.2, pp.127-151, 1987.
Faster shortest-path algorithms for planar graphs, Journal of computer and system sciences, vol.55, issue.1, pp.3-23, 1997. ,
Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs, Automata, Languages and Programming -38th International Colloquium, ICALP 2011, vol.6755, pp.135-146, 2011. ,
A separator theorem in minor-closed classes, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp.153-162, 2010. ,
Detecting a network failure, Internet Mathematics, vol.1, issue.1, pp.37-55, 2004. ,
The VC-dimension of set systems defined by graphs, Discrete Applied Mathematics, vol.77, issue.3, pp.237-257, 1997. ,
Planar diameter via metric compression, STOC, pp.152-163, 2019. ,
A separator theorem for planar graphs, SIAM Journal on Applied Mathematics, vol.36, issue.2, pp.177-189, 1979. ,
Spanning trees with low crossing number, vol.25, pp.103-123, 1991. ,
Bounded VC-dimension implies a fractional Helly theorem. Discrete & Computational Geometry, vol.31, pp.251-255, 2004. ,
Sparsity: graphs, structures, and algorithms, vol.28, 2012. ,
Structural sparsity, Russian Mathematical Surveys, vol.71, issue.1, p.79, 2016. ,
A simple linear-time algorithm for computing the center of an interval graph, International Journal of Computer Mathematics, vol.34, issue.3-4, pp.121-128, 1990. ,
On limited nondeterminism and the complexity of the VC dimension, Journal of Computer and System Sciences, vol.53, issue.2, pp.161-170, 1996. ,
Shallow Excluded Minors and Improved Graph Decompositions, SODA, vol.90, pp.462-470, 1994. ,
Fast approximation algorithms for the diameter and radius of sparse graphs, STOC, pp.515-524, 2013. ,
On the density of families of sets, Journal of Combinatorial Theory, Series A, vol.13, issue.1, pp.145-147, 1972. ,
A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific Journal of Mathematics, vol.41, issue.1, pp.247-261, 1972. ,
On the uniform convergence of relative frequencies of events to their probabilities, Measures of complexity, pp.11-30, 2015. ,
On spanning trees with low crossing numbers, Data structures and efficient algorithms, pp.233-249, 1992. ,
Separator theorems for minor-free and shallow minor-free graphs with applications, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp.37-46, 2011. ,