Loading [MathJax]/extensions/MathZoom.js
Displaying 241 –
260 of
532
A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm...
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows.
(1) The membership problem for Las Vegas finite automata is in NL.
(2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete.
(3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP.
These results provide partial answers to some open problems posed by Hromkovič
and Schnitger [Theoret....
Currently displaying 241 –
260 of
532