Skip to main content

Research Repository

Advanced Search

All Outputs (134)

Dense Gradient-based Features (DeGraF) for Computationally Efficient and Invariant Feature Extraction in Real-time Applications (2016)
Presentation / Conference Contribution
Katramados, I., & Breckon, T. (2016). Dense Gradient-based Features (DeGraF) for Computationally Efficient and Invariant Feature Extraction in Real-time Applications. In Proc. Int. Conf. on Image Processing (300-304). https://doi.org/10.1109/ICIP.2016.7532367

We propose a computationally efficient approach for the extraction of dense gradient-based features based on the use of localized intensity-weighted centroids within the image. Whilst prior work concentrates on sparse feature derivations or computati... Read More about Dense Gradient-based Features (DeGraF) for Computationally Efficient and Invariant Feature Extraction in Real-time Applications.

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing (2016)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., & Wastell, C. (2016). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. In P. Sankowski, & C. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms (ESA 2016) (1-18). https://doi.org/10.4230/lipics.esa.2016.10

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certai... Read More about Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing.

Efficient Comparison of Massive Graphs Through The Use Of 'Graph Fingerprints' (2016)
Presentation / Conference Contribution
Bonner, S., Brennan, J., Theodoropoulos, G., Kureshi, I., & McGough, A. (2016). Efficient Comparison of Massive Graphs Through The Use Of 'Graph Fingerprints'.

The problem of how to compare empirical graphs is an area of great interest within the field of network science. The ability to accurately but efficiently compare graphs has a significant impact in such areas as temporal graph evolution, anomaly dete... Read More about Efficient Comparison of Massive Graphs Through The Use Of 'Graph Fingerprints'.

SMS Spam Filtering using Probabilistic Topic Modelling and Stacked Denoising Autoencoder (2016)
Presentation / Conference Contribution
Al Moubayed, N., Breckon, T., Matthews, P., & McGough, A. (2016). SMS Spam Filtering using Probabilistic Topic Modelling and Stacked Denoising Autoencoder. In A. E. P. Villa, P. Masulli, & A. J. Pons Rivero (Eds.), Artificial neural networks and machine learning – ICANN 2016 : 25th International Conference on Artificial Neural Networks, Barcelona, Spain, September 6-9, 2016 ; proceedings. Part II (423-430). https://doi.org/10.1007/978-3-319-44781-0_50

In This paper we present a novel approach to spam filtering and demonstrate its applicability with respect to SMS messages. Our approach requires minimum features engineering and a small set of labelled data samples. Features are extracted using topi... Read More about SMS Spam Filtering using Probabilistic Topic Modelling and Stacked Denoising Autoencoder.

Finding cactus roots in polynomial time (2016)
Presentation / Conference Contribution
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Finding cactus roots in polynomial time. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (361-372). https://doi.org/10.1007/978-3-319-44543-4_28

A cactus is a connected graph in which each edge belongs to at most one cycle. A graph H is a cactus root of a graph G if H is a cactus and G can be obtained from H by adding an edge between any two vertices in H that are of distance 2 in H. We show... Read More about Finding cactus roots in polynomial time.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016). Well-quasi-ordering versus clique-width: new results on bigenic classes. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (253-265). https://doi.org/10.1007/978-3-319-44543-4_20

Daligault, Rao and Thomassé conjectured that if a hereditary class of graphs is well-quasi-ordered by the induced subgraph relation then it has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this conjecture is not true for infi... Read More about Well-quasi-ordering versus clique-width: new results on bigenic classes.

Minimal Disconnected Cuts in Planar Graphs (2016)
Journal Article
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696

The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar grap... Read More about Minimal Disconnected Cuts in Planar Graphs.

Lengths of words in transformation semigroups generated by digraphs (2016)
Journal Article
Cameron, P. J., Castillo-Ramirez, A., Gadouleau, M., & Mitchell, J. D. (2017). Lengths of words in transformation semigroups generated by digraphs. Journal of Algebraic Combinatorics, 45(1), 149-170. https://doi.org/10.1007/s10801-016-0703-9

Given a simple digraph D on n vertices (with n≥2n≥2 ), there is a natural construction of a semigroup of transformations ⟨D⟩⟨D⟩ . For any edge (a, b) of D, let a→ba→b be the idempotent of rank n−1n−1 mapping a to b and fixing all vertices other than... Read More about Lengths of words in transformation semigroups generated by digraphs.

Open problems on graph coloring for special graph classes (2016)
Presentation / Conference Contribution
Paulusma, D. (2016). Open problems on graph coloring for special graph classes. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (16-30). https://doi.org/10.1007/978-3-662-53174-7_2

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) for every edge uv∈Euv∈E. We survey known results... Read More about Open problems on graph coloring for special graph classes.

Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs (2016)
Presentation / Conference Contribution
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (456-471). https://doi.org/10.1007/978-3-662-53174-7_32

We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restr... Read More about Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs.

The stable fixtures problem with payments (2016)
Presentation / Conference Contribution
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2016). The stable fixtures problem with payments. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (49-63). https://doi.org/10.1007/978-3-662-53174-7_4

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph G=(N,E)G=(N,E), with an integer vertex capacity function b and an edge weighting w. The set N consists of a number of players that... Read More about The stable fixtures problem with payments.

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time (2016)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., Giakkoupis, G., & Kling, P. (2016). Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (1-14). https://doi.org/10.4230/lipics.icalp.2016.136

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication i... Read More about Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time.

Using contracted solution graphs for solving reconfiguration problems (2016)
Presentation / Conference Contribution
Bonsma, P., & Paulusma, D. (2016). Using contracted solution graphs for solving reconfiguration problems. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22–26, 2016, Kraków, Poland. https://doi.org/10.4230/lipics.mfcs.2016.20

We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions that decrease the graph size without... Read More about Using contracted solution graphs for solving reconfiguration problems.

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs (2016)
Presentation / Conference Contribution
Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016. https://doi.org/10.4230/lipics.icalp.2016.119

For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with do... Read More about Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

Stably computing order statistics with arithmetic population protocols (2016)
Presentation / Conference Contribution
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016). Stably computing order statistics with arithmetic population protocols. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (68:1-68:14). https://doi.org/10.4230/lipics.mfcs.2016.68

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Popula... Read More about Stably computing order statistics with arithmetic population protocols.

The friendship problem on graphs (2016)
Journal Article
Mertzios, G., & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 275-285

In this paper we provide a purely combinatorial proof of the Friendship Theorem, which has been first proven by P. Erdős et al. by using also algebraic methods. Moreover, we generalize this theorem in a natural way, assuming that every pair of nodes... Read More about The friendship problem on graphs.

Kempe equivalence of colourings of cubic graphs (2016)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59, 1-10. https://doi.org/10.1016/j.ejc.2016.06.008

Given a graph G=(V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by ex... Read More about Kempe equivalence of colourings of cubic graphs.

On algebras with many symmetric operations (2016)
Journal Article
Carvalho, C., & Krokhin, A. (2016). On algebras with many symmetric operations. International Journal of Algebra and Computation, 26(05), 1019-1032. https://doi.org/10.1142/s0218196716500429

An n-ary operation f is called symmetric if, for all permutations π of {1, . . . , n}, it satisfies the identity f(x1, x2, . . . , xn) = f(xπ(1), xπ(2), . . . , xπ(n) ). We show that, for each finite algebra A, either it has symmetric term operations... Read More about On algebras with many symmetric operations.

Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity (2016)
Journal Article
Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3), 914-944. https://doi.org/10.1007/s00453-016-0184-1

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interval or a permutation graph. In these pro... Read More about Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.