BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Patrick Prosser

Patrick Prosser contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsArtificial IntelligenceDistributed, Parallel, and Cluster ComputingDiscrete MathematicsComputer Science and Game TheoryLogic in Computer SciencePerformanceSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2020arXiv

A General Framework for Stable Roommates Problems using Answer Set Programming

The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are motivated by applications (e.g., the preference lists may be incomplete (SRI) and involve ties (SRTI)), and that try to find a more fair solution (e.g., Egalitarian SR). Unlike the Stable Marriage problem, every SR instance is not guaranteed to have a solution. For that reason, there are also variations of SR that try to find a good-enough solution (e.g., Almost SR). Most of these variations are NP-hard. We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set Programming, that is provable and general enough to solve many of such variations of SR. Our empirical analysis shows that SRTI-ASP is also promising for applications. This paper is under consideration for acceptance in TPLP.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Parallel Branch and Bound Algorithm for the Maximum Labelled Clique Problem

The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Empirical Algorithmics: draw your own conclusions

In an empirical comparisons of algorithms we might compare run times over a set of benchmark problems to decide which one is fastest, i.e. an algorithmic horse race. Ideally we would like to download source code for the algorithms, compile and then run on our machine. Sometimes code isn't available to download and sometimes resource isn't available to implement all the algorithms we want to study. To get round this, published results are rescaled, a technique endorsed by DIMACS, and those rescaled results included in a new study. This technique is frequently used when presenting new algorithms for the maximum clique problem. We demonstrate that this is unsafe, and that if carelessly used may allow us to draw conflicting conclusions from our empirical study.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Finding Maximum k-Cliques Faster using Lazy Global Domination

A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem. We use a state of the art maximum clique algorithm to show that this is feasible in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound

Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core thread-parallel adaptations of a state-of-the-art branch and bound algorithm for the maximum clique problem, and provide a novel explanation as to why they are successful. We show that load balance is sometimes a problem, but that the interaction of parallel search order and the most likely location of solutions within the search space is often the dominating consideration. We use this explanation to propose a new low-overhead, scalable work splitting mechanism. Our approach uses explicit early diversity to avoid strong commitment to the weakest heuristic advice, and late resplitting for balance. More generally, we argue that for branch and bound, parallel algorithm design should not be performed independently of the underlying sequential algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Ultrametric Constraint and its Application to Phylogenetics

A phylogenetic tree shows the evolutionary relationships among species. Internal nodes of the tree represent speciation events and leaf nodes correspond to species. A goal of phylogenetics is to combine such trees into larger trees, called supertrees, whilst respecting the relationships in the original trees. A rooted tree exhibits an ultrametric property; that is, for any three leaves of the tree it must be that one pair has a deeper most recent common ancestor than the other pairs, or that all three have the same most recent common ancestor. This inspires a constraint programming encoding for rooted trees. We present an efficient constraint that enforces the ultrametric property over a symmetric array of constrained integer variables, with the inevitable property that the lower bounds of any three variables are mutually supportive. We show that this allows an efficient constraint-based solution to the supertree construction problem. We demonstrate that the versatility of constraint programming can be exploited to allow solutions to variants of the supertree construction problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An n-ary Constraint for the Stable Marriage Problem

We present an n-ary constraint for the stable marriage problem. This constraint acts between two sets of integer variables where the domains of those variables represent preferences. Our constraint enforces stability and disallows bigamy. For a stable marriage instance with $n$ men and $n$ women we require only one of these constraints, and the complexity of enforcing arc-consistency is $O(n^2)$ which is optimal in the size of input. Our computational studies show that our n-ary constraint is significantly faster and more space efficient than the encodings presented in \cite{cp01}. We also introduce a new problem to the constraint community, the sex-equal stable marriage problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Diamond-free Degree Sequences

We introduce a new problem, CSPLib problem number 50, to generate all degree sequences that have a corresponding diamond-free graph with secondary properties. This problem arises naturally from a problem in mathematics to do with balanced incomplete block designs; we devote a section of this paper to this. The problem itself is challenging with respect to computational effort arising from the large number of symmetries within the models. We introduce two models for this problem. The second model is an improvement on the first, and this improvement largely consists of breaking the problem into two stages, the first stage producing graphical degree sequences that satisfy arithmetic constraints and the second part testing that there exists a graph with that degree sequence that is diamond-free.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributing an Exact Algorithm for Maximum Clique: maximising the costup

We take an existing implementation of an algorithm for the maximum clique problem and modify it so that we can distribute it over an ad-hoc cluster of machines. Our goal was to achieve a significant speedup in performance with minimal development effort, i.e. a maximum costup. We present a simple modification to a state-of-the-art exact algorithm for maximum clique that allows us to distribute it across many machines. An empirical study over large hard benchmarks shows that speedups of an order of magnitude are routine for 25 or more machines.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Exact Algorithms for Maximum Clique: a computational study

We investigate a number of recently reported exact algorithms for the maximum clique problem (MCQ, MCR, MCS, BBMC). The program code used is presented and critiqued showing how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platforms influence algorithm behaviour. The minimum width order (smallest-last) is investigated, and MCS is broken into its consituent parts and we discover that one of these parts degrades performance. It is shown that the standard procedure used for rescaling published results is unsafe.

0 citations0 reviewsNo code linkedOpen access