Algorithm for finding connected subgraph of a vertex weighted graph with a sum close to a given value -

-

given vertex weighted graph g (depicted below), vertex v graph , integer value x, there known algorithm finding connected sub graph of g such target vertex in sub graph , sum of weights of sub graph close x possible? moreover, if exact match of x cannot found, algorithm should still return sub graphs closest x possible.

some examples given graph below:

v = f, x = 12. a,b,f,i , f,g,c,d solutions.

v = c, x = 16. c,d,e,h solution.

vertex weighted simple graph.

finding solution looks variant of knapsack problem me, additional constraint items in knapsack must form connected graph.

one approach check possible subgraphs containing v , searching maximum weight (up x):

you use kind of greedy algorithm, starting node v , adding 1 adjacent node after another, keeping track of total subgraph weight. if reach x, finished, if overshoot x, must backtrack , select other nodes subgraph. during whole algorithm, keep track of "best" subgraph, if no exact solution found in end, still have best approximation.

you can choose order of nodes add subgraph utilizing heuristic, e.g. best fit, affects run time, not quality of results..


Comments

Post a Comment

Popular posts from this blog

Android : Making Listview full screen -

-
<linearlayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" android:layout_width="match_parent" android:layout_height="match_parent" android:orientation="vertical" tools:context=".mainactivity"> <edittext android:layout_margintop="5dp" android:layout_width="match_parent" android:layout_height="50dp" android:background="@drawable/location_edittext" android:id="@+id/locationeditext" android:textsize="15sp" android:textcolor="#999" android:paddingleft="15dp" /> <com.example.ravi_gupta.slider.viewpagercustomduration android:layout_width="wrap_content" android:layout_height="0dp" android:id="@+id/viewpager" android:scrollbarstyle="outsideoverlay" android:layout_weight="0.5&quo
Read more

javascript - Parse JSON from the body of the POST -

-
i'm using cameratag.com record video on website. service can send json response server can save data database. don't know how proceed here: the documentation states please note json repsonse passed in body of post , not form parameters. here example of how parse response in ruby: data = json.parse(request.raw_post) video_uuid = data["uuid"] but don't know how data on javascript. i'm not experienced in js please bare me :) post sample: { "uuid": "00012710-4b65-0131-ffe6-22000a499ea4", "camera_uuid": "98373a20-79ee-0130-3e42-1231390fcc11", "created_at": "2013-12-20t05:25:02.000z", "percent_complete": 100, "short_code": "kktb4q", "metadata": { }, "state": "published", "recorded_from": "http://singwho.com", "publish_type": null, "formats": [ { "name&qu
Read more

javascript - Chrome Extension: Interacting with iframe embedded within popup -

-
i writing chrome extension needs interact urls user not have open. therefore using hidden iframes embedded within popup, , attempting click button within iframe. however, receiving same origin policy error. know possible extension interact iframes of different domain via content scripts when iframe on tab user has open, not sure if possible use content scripts interact iframes directly in popup. here code: manifest.json "content_scripts": [ { "js": [ "bin/jquery.min.js", "interaction.js" ], "all_frames": true, "run_at": "document_start", "matches": [ "http://*/*", "https://*/*" ] }], "permissions": [ "activetab", "tabs", "http://*/", "https://*/" ], interaction.js $(document).ready(function() { $('div#iframes').append("<iframe id='shop' src=
Read more