Positive and negative length-bound reachability constraints

Simple item page
dc.contributor.authorQuesada, Luis
dc.contributor.authorBrown, Kenneth N.
dc.contributor.editorMichel, Laurent D.
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2021-10-20T13:57:19Z
dc.date.available2021-10-20T13:57:19Z
dc.date.issued2021-10-15
dc.date.updated2021-10-20T13:43:00Z
dc.description.abstractIn many application problems, including physical security and wildlife conservation, infrastructure must be configured to ensure or deny paths between specified locations. We model the problem as sub-graph design subject to constraints on paths and path lengths, and propose length-bound reachability constraints. Although reachability in graphs has been modelled before in constraint programming, the interaction of positive and negative reachability has not been studied in depth. We prove that deciding whether a set of positive and negative reachability constraints are satisfiable is NP complete. We show the effectiveness of our approach on decision problems, and also on optimisation problems. We compare our approach with existing constraint models, and we demonstrate significant improvements in runtime and solution costs, on a new problem set.en
dc.description.sponsorshipScience Foundation Ireland (16/SP/3804; 12/RC/2289-P2)en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.articleid46en
dc.identifier.citationQuesada, L. and Brown, K. N. (2021) 'Positive and negative length-bound reachability constraints', 27th International Conference on Principles and Practice of Constraint Programming (CP 21), Montpellier, France, 25 - 29 October, 46 (16pp). doi: 10.4230/LIPIcs.CP.2021.46en
dc.identifier.doi10.4230/LIPIcs.CP.2021.46en
dc.identifier.endpage16en
dc.identifier.isbn978-3-95977-211-2
dc.identifier.issn1868-8969
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/12114
dc.language.isoenen
dc.publisherSchloss Dagstuhl – Leibniz-Zentrum für Informatiken
dc.relation.ispartof27th International Conference on Principles and Practice of Constraint Programming (CP 21), Montpellier, France, 25 - 29 October 2021
dc.relation.ispartofLeibniz International Proceedings in Informatics (LIPIcs)
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs);
dc.rights© 2021, Luis Quesada and Kenneth N. Brown. Licensed under Creative Commons License CC-BY 4.0.en
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subjectReachability constraintsen
dc.subjectGraph connectivityen
dc.subjectConstraint programmingen
dc.titlePositive and negative length-bound reachability constraintsen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LIPIcs-CP-2021-46.pdf
Size:
1.3 MB
Format:
Adobe Portable Document Format
Description:
Published Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Insight Centre for Data Analytics - Conference Items