Question

For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?

a.

tree graphs

b.

bipartite graphs

c.

both a and b

d.

none of the mentioned

Posted under Formal Languages and Automata Theory

Answer: (a).tree graphs

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?

Add Comment

Similar Questions

Discover Related MCQs

Q. Hamilton circuit problem can have the following version/s as per the input graph:

View solution

Q. Hamilton Circuit problem is a special case of ____________

View solution

Q. Which of the following cannot solve Hamilton Circuit problem?

View solution

Q. State true or false:
Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.

View solution

Q. Fibonacci number falls in the category of _________ combinatorics.

View solution

Q. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:

View solution

Q. PSPACE is strictly the super set of:

View solution

Q. Savitch theorem relates to which of the following:

View solution

Q. The class PSPACE is closed under the following operations:

View solution

Q. Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE

View solution

Q. NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?

View solution

Q. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.
State true or false:

View solution

Q. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.

View solution

Q. Complement of all the problems in PSPACE is ________

View solution

Q. Which of the following PSPACE can be characterized into?

View solution

Q. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.

View solution

Q. Which of the following options match the given statement:
Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.

View solution

Q. Which of the following are probalistic algorithms?

View solution

Q. Which of the following algorithms are probably correct as well as fast?

View solution

Q. Prisonner’s dilemma can be related to the following:

View solution

View All MCQs on Formal Languages and Automata Theory

Suggested Topics

Are you eager to expand your knowledge beyond Formal Languages and Automata Theory? We've curated a selection of related categories that you might find intriguing.

Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!

CSS

Polish your web design skills with our CSS MCQs. Learn about selectors, properties,...

Object Oriented Programming Using C++

Enhance your programming skills with our MCQs on Object Oriented Programming using...

Human Computer Interaction

Enhance your knowledge of Human-Computer Interaction with our specialized MCQs....

C# programming

Hone your skills in the C# language with our MCQs. Understand data types, operators,...

MATLAB

Hone your computational mathematics skills with our MATLAB MCQs. Understand...

Digital Logic Design

Understand the foundation of digital computers with our Digital Logic Design MCQs....

Artificial Intelligence

Get started on the path to the future with our Artificial Intelligence MCQs. Covering...

Digital Image Processing (DIP)

Delve into the techniques of enhancing digital images with our Digital Image...

PHP

Venture into server-side scripting with our PHP MCQs. Cover everything from syntax...