Given an undirected graph $G$ (can be cyclic) with the promise that all its faces have $3$ sides, is it possible to find the minimum distance between a source and any other vertices in LogSpace or in LogDCFL, at least under the constraint that between any two vertices there are polynomially many paths?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ @StefanKohl: Please limit the flood of minor edits to a handful per day. See meta.mathoverflow.net/questions/599 . $\endgroup$– Emil JeřábekOct 16, 2015 at 15:42
-
$\begingroup$ @EmilJeřábek: o.k.. $\endgroup$– Stefan Kohl ♦Oct 16, 2015 at 15:45
-
3$\begingroup$ What do you mean by "all its faces have 3 sides"? Faces are not a concept that makes sense for arbitrary (non-planar) graphs. And when you say "between any two vertices there are polynomially many paths", you mean simple paths, right? But in an undirected graph that's still a very strong restriction. $\endgroup$– David EppsteinOct 17, 2015 at 4:43
Add a comment
|