Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings Algoritma Tepat untuk Masalah Peletakan Anak Panah dalam Lukisan Graf Terarah

Naoto KIDO, Sumio MASUDA, Kazuaki YAMAGUCHI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Kami menganggap masalah meletakkan anak panah, yang menunjukkan arah setiap tepi dalam lukisan graf terarah, tanpa menjadikannya bertindih dengan anak panah, bucu dan tepi lain sebanyak mungkin. Dua kaedah berikut telah dicadangkan untuk masalah ini. Satu ialah algoritma yang tepat untuk kes di mana kedudukan setiap anak panah dihadkan kepada beberapa titik diskret. Yang lain ialah algoritma heuristik untuk kes di mana anak panah dibenarkan bergerak secara berterusan pada setiap tepi. Dalam makalah ini, kami menganggap bahawa kedudukan anak panah tidak terhad kepada titik diskret dan mencadangkan algoritma yang tepat untuk masalah mencari peletakan anak panah supaya (a) jumlah wajaran bilangan pertindihan dengan tepi, bucu dan anak panah lain adalah diminimumkan dan (b) jumlah jarak antara anak panah dan bucu terminal tepinya diminimumkan sebagai objektif kedua. Kaedah yang dicadangkan menyelesaikan masalah ini dengan mengurangkannya kepada masalah pengaturcaraan linear integer bercampur. Oleh kerana ini ialah algoritma masa eksponen, kami menambah prosedur mudah sebagai prapemprosesan untuk mengurangkan masa berjalan. Keputusan eksperimen menunjukkan bahawa kaedah yang dicadangkan boleh mencari peletakan anak panah yang lebih baik daripada kaedah sebelumnya dan prosedur untuk mengurangkan masa berjalan adalah berkesan.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.11 pp.1481-1489
Tarikh penerbitan
2019/11/01
Diumumkan
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.E102.A.1481
Jenis Manuskrip
PAPER
kategori
Algoritma dan Struktur Data

Pengarang

Naoto KIDO
  Kobe University
Sumio MASUDA
  Kobe University
Kazuaki YAMAGUCHI
  Kobe University

Kata kunci

Contents [show]