Archive of posts with tag 'SergioCabello'

• Sergio Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

  Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

  Sergio Cabello
  Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia

  2017/09/26 Tue 4PM-5PM (Room 3433, Bldg. E6-1)

  We show how to compute for n-vertex planar graphs in roughly O(n^11/6) expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time O(n^c) for some constant c<2, even when restricted to undirected, unweighted planar graphs.

  Tags:

  • SergioCabello

• Sergio Cabello, The Fibonacci dimension of a graph

  The Fibonacci dimension of a graph

  Sergio Cabello
  Dept. of Mathematics, University of Ljubljana, Slovenia

  2010/2/10 Wed, 4PM-5PM

  The Fibonacci dimension fdim(G) of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into the f-dimensional Fibonacci cube. We will see combinatorial relations between the Fibonacci dimension and the isometric or lattice dimension, and establish the Fibonacci dimension for certain families of graphs. Finally, we will discuss the problem of computing the Fibonacci dimension, namely, its NP-hardness and approximation algorithms.

  Joint work with D. Eppstein and S. Klavžar. Manuscript available at arxiv:0903.2507.

  Tags:

  • SergioCabello