2
$\begingroup$

Input: Given graph $G=(V,E)$ vertex labeling in some order

Output: Change the labeling of vertices's such that labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ according least index given in input. Next labeling the neighbors of least index neighbor of $v_1$. I.e. $v_1=u_1$ and neighbors of $v_1$ as $u_2,u_3,...$. so .. on

For example: input: $G=(V,E)$ and $V=\{v_1,v_2,v_3,v_4,v_4,v_5,v_6\}, E=\{v_1v_3,v_1v_5,v_1v_6,v_2v_3,v_2v_4,v_2v_5,v_2v_6\}$

Output: $G'=(U,E')$ and $U=\{u_1,u_2,u_3,u_4,u_4,u_5,u_6\}, E'=\{u_1u_2,u_1u_3,u_1u_4,u_2u_5,u_3u_5,u_4u_5,u_5u_6\}$

Can there be a algorithm for above process in logspace? I trying with BFS but not working in logspace. Can any one help me out.

See for defination of Lexicographic BFS(en.wikipedia.org/wiki/Lexicographic_breadth-first_search)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I don't see how this differs from en.wikipedia.org/wiki/Lexicographic_breadth-first_search ; are you asking whether LBFS can be implemented in logspace? $\endgroup$
    – András Salamon
    Apr 30, 2017 at 15:04
  • 1
    $\begingroup$ @AndrasSalamon nice catching point. Can LBFS implemented in logspace? $\endgroup$
    – Diamond
    May 1, 2017 at 2:43
  • 1
    $\begingroup$ I suggest you change the title to "Can Lexicographic BFS be implemented in logspace?", start the post with that question (using ">"), including a link to the wikipedia page, and then you could use the material from current post simply as the definition/example of LBFS. $\endgroup$
    – Joshua Grochow
    May 1, 2017 at 5:00
  • 3
    $\begingroup$ The introduction to this paper eccc.weizmann.ac.il/report/2010/043 suggests that no implementation of LexBFS in logspace is known: otherwise the authors could compute a perfect elimination ordering in logspace, which they explicitly say they avoid. $\endgroup$
    – Sasho Nikolov
    May 1, 2017 at 10:01
  • 1
    $\begingroup$ I'm pretty sure that computing the ordering is hard for $P$, by a reduction from (monotone) Circuit Evaluation. You construct a graph corresponding to the gates s.t. computing the lex first bfs ordering evaluates the gates of the circuit. Can't recall the reference at the moment, though. $\endgroup$
    – Ryan Williams
    May 2, 2017 at 12:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy