algorithm - Accommodate maximum peoples in tour -


i have arrange tour. there n peoples want attend tour. of them enemies each other. (enemy of enemy may or may not enemy. if enemy of b, b enemy of a) if accommodate person in tour, can not accommodate enemy.

now want accommodate maximum possible number of persons in tour. how can find number?

ex: if there 5 tourists, , let's call them a-e. enemy b , d, b enemy of e, , c enemy of d.

      b   c   d   e   +---+---+---+---+---+ | - | x |   | x |   |   +---+---+---+---+---+ b | x | - |   |   | x |   +---+---+---+---+---+ c |   |   | - | x |   |   +---+---+---+---+---+ d | x |   | x | - |   |   +---+---+---+---+---+ e |   | x |   |   | - |   +---+---+---+---+---+

in case following trips possible: empty, a, b, c, d, e, ac, ae, bc, bd, ace, ce, de etc. out of these, best tour ace accommodates 3 tourist , hence answer 3.

my approach:

  • i tried looping , trying combinations bitmaps, slow.
  • i using dfs trying find better method.
  • i tried work creating friendship graph , prepare some
    spanning tree. doesn't work can travel b , b can
    travel c not guarantee , travel c.
  • i tried creating enemity graph , finding weak links ended clueless.

i thankful, if can give me hint or point resource solve problem.

create graph tourists :

  • each node tourist
  • if 2 tourists enemies draw edge between them
  • find maximum independent set

there detailed algorithms finding maximum independent set in paper: algorithms maximum independent sets

and parallel approach has been provided in one:lecture notes on parallel algorithm generating maximal independent set

and this java implementation.


Comments

Post a Comment

Popular posts from this blog

Android layout hidden on keyboard show -

i have strange problem layout. when tap on edittext , keyboard shown edittext stay on bottom , when tap on to hide keyboard , keyboard hides , edittext go should when want input text. when tap again, keyboard shown , edittext goes down behind keyboard... <relativelayout android:layout_width="match_parent" android:layout_height="match_parent" > <scrollview android:layout_width="match_parent" android:layout_height="fill_parent" android:above="@+id/rl_commands"> <textview android:layout_width="match_parent" android:layout_height="wrap_content"/> </scrollview> <relativelayout android:layout_width="match_parent android:layout_height="24dp" android:id="@+id/rl_commands" android:alignparentbottom="true">
Read more

google app engine - 403 Forbidden POST - Flask WTForms -

i have flask application running on google app engine. trying submit form built using wtform , keep getting following error. 403 forbidden: don't have permission access requested resource. either read-protected or not readable server. location.html (part of code) <form method=post action="/home/location"> .... <button type="submit" class="btn btn-primary" value="submit"> directions </button> </form> main.py @app.route('/home/location', methods=['post', 'get']) def location(): form = cfcdirections.direction(request.form) print(request.method) if request.method == 'post' , form.validate(): print("after if") directions = cfcdirections() street_no = directions.no street = directions.street suburb = directions.suburb postcode = directions.postcode
Read more

c - Why would PK11_GenerateRandom() return an error -8023? -

i looking through internet trying find source of pk11_generaterandom() function see why function fail. have program uses function when moved new flavor of linux, fails after forking ( fork() ) since not believe there problem nss, suspect doing incorrectly disregarded in older versions of linux new 1 there issue. the openssl package same on 'good' , 'bad' server: openssl 0.9.8e-fips-rhel5 01 jul nss rpm differs though. 'good' has nss-3.12.2.0-2.el5 and bas has version nss-3.15.3-4.el5_10 the 'good' server uses quite obsolete linux: linux 2.6.18-128.el5 #1 smp wed jan 21 08:45:05 est 2009 x86_64 x86_64 x86_64 gnu/linux enterprise linux enterprise linux server release 5.3 (carthage) red hat enterprise linux server release 5.3 (tikanga) the 'bad' server newer: linux bad 2.6.18-371.4.1.el5 #1 smp wed jan 29 11:05:49 pst 2014 x86_64 x86_64 x86_64 gnu/linux oracle linux server release 5.10 red hat enterprise linux server release
Read more