Dalam makalah mereka Perkiraan Jarak Orakel , Thorup dan Zwick menunjukkan bahwa untuk setiap grafik tanpa arahan tertimbang, adalah mungkin untuk membangun struktur data ukuran yang dapat mengembalikan ( 2 k - 1 ) -approximate jarak antara setiap pasangan simpul dalam grafik.O ( k n1 + 1 /...
Masalah GI dan Knot keduanya merupakan masalah dalam menentukan kesetaraan struktural dari objek matematika. Apakah ada hasil yang membuat koneksi di antara mereka? Koneksi bagus masalah simpul ke fisika statistik telah dieksplorasi melalui simpul polinomial , apakah ada hasil yang serupa untuk ?G...
Saya bertanya-tanya bagaimana menemukan ketebalan grafik tidak berarah jarang. Maksud saya jarang . Maksud saya adalah kompleksitas waktu terendah.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Saya memikirkan beberapa modifikasi pada algoritma Tarjan untuk grafik tidak berarah, tetapi saya tidak menemukan hasil...
Lemma: Dengan asumsi kesetaraan eta kita memilikinya (\x -> ⊥) = ⊥ :: A -> B. Bukti: ⊥ = (\x -> ⊥ x)dengan kesetaraan eta, dan (\x -> ⊥ x) = (\x -> ⊥)dengan pengurangan di bawah lambda. Laporan Haskell 2010, bagian 6.2 menentukan seqfungsi dengan dua persamaan: seq :: a -> b...
The Paley grafik P q adalah mereka yang simpul-set diberikan oleh bidang yang terbatas GF (q), untuk kekuatan utama q≡1 (mod 4), dan di mana dua simpul yang berdekatan jika dan hanya jika mereka berbeda oleh 2 untuk beberapa a ∈ GF (q). Dalam kasus q adalah prima, bidang hingga GF (q) hanyalah...
Ini adalah pertanyaan yang terinspirasi oleh masalah pemotongan bebas-H . Diberikan grafik, partisi dari simpulnya mengatur menjadi r bagian V 1 , V 2 , ... , V r adalah H -gratis jika G [ V i ] tidak menginduksi salinan H untuk semua i , 1 ≤ i ≤ r .VVVrrrV1,V2,…,VrV1,V2,…,VrV_1, V_2, \ldots,...
Untuk grafik tanpa arahan mana semua pohon pencarian pertama-dalam (untuk semua simpul awal yang memungkinkan dan untuk semua pilihan tetangga mana yang dicari terlebih dahulu) jalur yang diarahkan? Artinya, setiap pohon DFS harus hanya memiliki satu daun, dan setiap simpul lainnya harus memiliki...
Seperti judulnya, apa definisi yang benar dari -tree? Ada beberapa kertas yang berbicara tentang k -trees dan parsial k -trees sebagai definisi alternatif untuk grafik dengan treewidth dibatasi, dan saya telah melihat banyak definisi yang tampaknya tidak benar. Misalnya, setidaknya satu tempat...
Misalkan kita memiliki seperangkat S grafik (grafik berhingga, tetapi sejumlah tak terbatas dari mereka) dan sekelompok P permutasi yang bekerja pada S. Instance: P permutasi di P. Pertanyaan: Apakah ada grafik g di S yang menerima p automorfisme? Apakah ini masalah NP-complete untuk...
Pertimbangkan masalah berikut. Input: Grafik tidak berarah . Output: Grafik H yang merupakan minor G dengan kepadatan tepi tertinggi di antara semua anak di bawah umur G , yaitu, dengan rasio tertinggi | E ( H ) | / | V ( H ) |
Dalam Bundeswettberweb Infomatik 2010/2011, ada masalah yang menarik: Untuk fix , temukan minimal k dan peta φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , ... , k } , sedemikian sehingga tidak ada tiga ( i , j ) , ( i + l , j ) , ( i + l , j + l ) dengan φ (
Saya sudah mencoba relaksasi LP berikut set independen maksimum max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Saya mendapatkan 1/21/21/2 untuk setiap variabel untuk setiap graf non-bipartit kubik aku...
Latar Belakang Pertanyaan ini dimotivasi oleh permainan papan yang disebut 'Drakula'. Dalam game ini ada satu vampir dan empat pemburu, tujuan para pemburu adalah untuk menangkap vampir. Permainan berlangsung di Eropa. Permainan terlihat sebagai berikut: 1. Pemain pemburu menempatkan semua...
Kita diberi grafik asiklik terarah dengan angka yang terkait dengan setiap simpul ( g : V → N ), dan nomor target TG=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N} .T∈NT∈NT\in \mathbb{N} The DAG bagian sum masalah (mungkin ada dengan nama yang berbeda, referensi akan menjadi besar) menanyakan...
O ( log n )HAI(catatann)O({\log}n)O ( m + n )HAI(m+n)O(m+n) Apa algoritma paralel yang paling dikenal untuk st-konektivitas dalam grafik planar terarah? Silakan sebutkan waktu berjalan, algoritma deterministik / acak dan model PRAM yang digunakan (dengan asumsi jumlah prosesor adalah...
Dalam makalah oleh Kempe-Kleinberg-Tardos, Penulis mengusulkan algoritma rakus berdasarkan fungsi submodular untuk menentukan paling berpengaruh node dalam grafik, dengan aplikasi untuk jaringan sosial.kkk Pada dasarnya algoritma berjalan sebagai berikut: S= e m p t y s e t S=emhalty setS = {\rm...
Saya tertarik untuk memahami struktur kelas grafik sehingga tidak ada subgraph yang diinduksi vertex pada empat simpul yang merupakan pencocokan sempurna. Lain berbeda untuk setiap empat simpul a , b , c , d di G jika sebuah b dan c d tepi yang kemudian grafik harus memiliki setidaknya satu lagi...
Misalkan ada grafik . Saya ingin menguji apakah V dapat dipartisi menjadi dua set disjoint V 1 dan V 2 sehingga subgraph yang diinduksi oleh V 1 dan V 2 adalah grafik satuan interval.G = ( V, E)G=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Saya tahu tentang NP-kelengkapan penentuan angka interval...
Saya tertarik pada kompleksitas masalah set mendominasi (DSP) di beberapa kelas grafik tertentu yang merupakan subkelas dari grafik chordal . Grafik adalah grafik lintasan yang tidak diarahkan jika itu adalah grafik persimpangan-simpul dari keluarga lintasan di beberapa pohon yang tidak diarahkan....
Mengingat grafik planar, satu kaleng menanamkan dalam waktu linier menyeberang bebas ke dalam jaringan. Saya tertarik apakah ada algoritma yang efisien diketahui garis lurus menanamkan grafik planar menyeberang bebas ke dalam n c × n c grid, untuk beberapa c kecil , sehingga sudut minimum antara...