Skip to main content

Research Repository

Advanced Search

Outputs (127)

Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width (2014)
Journal Article
Bordewich, M., & Kang, R. (2014). Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width. Electronic Journal of Combinatorics, 21(4), Article 19

Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument,... Read More about Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2014)
Journal Article
Mertzios, G., & Spirakis, P. (2016). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. Algorithmica, 74(1), 385-414. https://doi.org/10.1007/s00453-014-9949-6

The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring cannot be solved in... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

Cross-layer optimisation for topology design of wireless multicast networks via network coding (2014)
Presentation / Conference Contribution
Vien, Q. T., Tu, W., Nguyen, H. X., & Trestian, R. (2014, September). Cross-layer optimisation for topology design of wireless multicast networks via network coding. Presented at Proceedings Conference on Local Computer Networks LCN, Edmonton, Canada

One of the main challenges towards reliable multicast transmissions over wireless networks is the dynamics of the wireless links (e.g. wireless errors, fading, interference, collisions, etc.) that can cause retransmissions overhead over the limited a... Read More about Cross-layer optimisation for topology design of wireless multicast networks via network coding.

A multi-rate multi-channel multicast algorithm in wireless mesh networks (2014)
Presentation / Conference Contribution
Tu, W. (2014, September). A multi-rate multi-channel multicast algorithm in wireless mesh networks. Presented at Proceedings Conference on Local Computer Networks LCN, Edmonton, Canada

Devices in wireless mesh networks can operate on multiple channels and automatically adjust their transmission rates for the occupied channels. This paper shows how to improve performance-guaranteed multicasting transmission coverage for wireless mul... Read More about A multi-rate multi-channel multicast algorithm in wireless mesh networks.

Oracle Tractability of Skew Bisubmodular Functions (2014)
Journal Article
Huber, A., & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics, 28(4), 1828-1837. https://doi.org/10.1137/130936038

In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use th... Read More about Oracle Tractability of Skew Bisubmodular Functions.

The Critical Role of Profiles in Social E-Learning Design (2014)
Presentation / Conference Contribution
Shi, L., Cristea, A. I., & Hadzidedic, S. (2014, October). The Critical Role of Profiles in Social E-Learning Design. Presented at 15th Annual Conference on Information Technology Education (SIGITE), Atlanta, Georgia, US

Evidence points to the fact that the integration of Social Networking Sites (SNS) features, into e-learning environments has been highly accepted by students, because of its benefits of improving the learning experience. Yet, not enough attention has... Read More about The Critical Role of Profiles in Social E-Learning Design.

A steganalytic algorithm for 3D polygonal meshes (2014)
Presentation / Conference Contribution
Yang, Y., Pintus, R., Rushmeier, H., & Ivrissimtzis, I. (2014, October). A steganalytic algorithm for 3D polygonal meshes. Presented at 2014 IEEE International Conference on Image Processing (ICIP), Paris, France

We propose a steganalytic algorithm for watermarks embedded by Cho et al.'s mean-based algorithm [1]. The main observation is that while in a clean model the means of Cho et al.'s normalized histogram bins are expected to follow a Gaussian distributi... Read More about A steganalytic algorithm for 3D polygonal meshes.

Closing complexity gaps for coloring problems on H-free graphs (2014)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 237, 204-214. https://doi.org/10.1016/j.ic.2014.02.004

If a graph G contains no subgraph isomorphic to some graph H , then G is called H -free. A coloring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that no two adjacent vertices have the same color, i.e., c(u)≠c(v) if uv∈E; if |c(V)|⩽k then c is a k... Read More about Closing complexity gaps for coloring problems on H-free graphs.