The Library
An exact algorithm for knot-free vertex deletion
Tools
Ramanujan, M. S., Sahu, Abhishek, Saurabh, Saket and Verma, Shaily (2022) An exact algorithm for knot-free vertex deletion. In: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria, 22—26 Aug 2022, 241 78:1-78:15. ISBN 9783959772563. doi:10.4230/LIPIcs.MFCS.2022.78 ISSN 1868-8969.
|
PDF
WRAP-exact-algorithm-knot-free-vertex-deletion-Ramanujan-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (824Kb) | Preview |
Official URL: https://drops.dagstuhl.de/opus/volltexte/2022/1687...
Abstract
The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u,v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis -- Data processing , Computational complexity, Computable functions, Electronic data processing -- Distributed processing, Computer algorithms | |||||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||||||||
Publisher: | Schloss Dagstuhl — Leibniz-Zentrum für Informatik | |||||||||||||||
Place of Publication: | Dagstuhl, Germany | |||||||||||||||
ISBN: | 9783959772563 | |||||||||||||||
ISSN: | 1868-8969 | |||||||||||||||
Official Date: | 22 August 2022 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 241 | |||||||||||||||
Page Range: | 78:1-78:15 | |||||||||||||||
DOI: | 10.4230/LIPIcs.MFCS.2022.78 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 10 November 2022 | |||||||||||||||
Date of first compliant Open Access: | 11 November 2022 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Vienna, Austria | |||||||||||||||
Date(s) of Event: | 22—26 Aug 2022 | |||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year