Answered: We have to create a seating plan for…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

We have to create a seating plan for conference. As an input, we have:

All people - set named AP

Set of people, that has to sit together - set named ST

Set of people, that can't sit together - set named NST

Number of tables - named NT

Number of seats at the table - named NS

Relation between elements of sets NT and NP is binary ireflexive.

Prove, that out problem P is NP-complete problem. Reduce from Graph Coloring Problem to our P problem.

I think, we have to construct a Turing machine working in polynomial time (there is no need to construct, just describe the working process of Touring machine). Also describe the reduction function. In my opinion, output should be string <AP>/<ST>/<NST>/<NT>/<NS>. The number of tables NT should be determined from graph, also the number of seats at the table NS. That's what I think.

Thank you!

Expert Solution

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions