- ปัญหานักผจญเพลิงด้วยงบประมาณขั้นต่ำ: ความแข็งและการประมาณอัลกอริธึมสำหรับกราฟดิสก์หน่วย (arXiv)
ผู้แต่ง: ดิปเทนฑุ ฉัตเทอร์จี, ริชิราช ภัตตาจารย์ยา
บทคัดย่อ : กราฟดิสก์หน่วยคือชุดของกราฟที่แสดงถึงจุดตัดของกราฟดิสก์และกราฟช่วงเวลา กราฟเหล่านี้มีความสำคัญอย่างยิ่งเนื่องจากมีความคล้ายคลึงกันทางโครงสร้างกับเครือข่ายการสื่อสารไร้สาย ปัญหาของนักผจญเพลิงบนกราฟดิสก์หน่วยนั้นน่าสนใจ เนื่องจากเป็นการจำลองไวรัสที่แพร่กระจายในเครือข่ายไร้สายและขอวิธีแก้ไขเพื่อหยุดยั้งมัน ในบทความนี้ เราพิจารณาปัญหานักดับเพลิงตามงบประมาณขั้นต่ำ โดยมีเป้าหมายเพื่อกำหนดจำนวนนักดับเพลิงขั้นต่ำที่ต้องการ และโหนดที่จะวางพวกเขาในแต่ละครั้งทันทีเพื่อบันทึกชุดจุดยอดที่กำหนดของกราฟที่กำหนดและโหนดแยกไฟ . เราแสดงให้เห็นว่าปัญหานักดับเพลิง MIN-BUDGET ในกราฟดิสก์หน่วยคือ NP-Hard นอกจากนี้เรายังนำเสนออัลกอริธึมการประมาณค่าคงที่
2. กราฟดิสก์หน่วยไฮเปอร์โบลิกอย่างมาก (arXiv)
ผู้แต่ง : Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Daniel Stephan
บทคัดย่อ : คลาสของกราฟดิสก์หน่วยแบบยุคลิดเป็นหนึ่งในคลาสกราฟพื้นฐานและได้รับการศึกษามาเป็นอย่างดีซึ่งมีรูปทรงเรขาคณิตพื้นฐานอยู่ ในบทความนี้ เราระบุคลาสนี้เป็นกรณีพิเศษในคลาสที่กว้างกว่าของกราฟดิสก์หน่วยไฮเปอร์โบลิก และแนะนำกราฟดิสก์หน่วยไฮเปอร์โบลิกอย่างยิ่งในฐานะคู่กันโดยธรรมชาติกับตัวแปรแบบยุคลิด ตรงกันข้ามกับโครงสร้างคล้ายตารางที่แสดงโดยกราฟดิสก์หน่วยยุคลิด เครือข่ายไฮเปอร์โบลิกอย่างยิ่งมีโครงสร้างแบบลำดับชั้น ซึ่งพบเห็นได้ในเครือข่ายโลกแห่งความจริงที่ซับซ้อนเช่นกัน เราตรวจสอบคุณสมบัติพื้นฐานของกราฟดิสก์หน่วยไฮเพอร์โบลิกอย่างมาก รวมถึงส่วนที่อยู่ติดกันและการก่อตัวของกลุ่ม และใช้ข้อมูลเชิงลึกที่ได้รับเพื่อแสดงให้เห็นว่าคลาสนี้มีประโยชน์สำหรับการพัฒนาและการวิเคราะห์อัลกอริธึมกราฟ โดยเฉพาะอย่างยิ่ง เราพัฒนารูปแบบการกำหนดเส้นทางที่เรียบง่ายและวิเคราะห์ประสิทธิภาพของมันบนกราฟดิสก์หน่วยไฮเปอร์โบลิกอย่างมาก เพื่อพิสูจน์ว่าการกำหนดเส้นทางสามารถทำได้อย่างมีประสิทธิภาพบนเครือข่ายดังกล่าวมากกว่าทั่วไป
