Skip to main content

Research Repository

Advanced Search

All Outputs (72)

Transversals of subtree hypergraphs and the source location problem in digraphs (2008)
Journal Article
Heuvel van den, J., & Johnson, M. (2008). Transversals of subtree hypergraphs and the source location problem in digraphs. Networks, 51(2), 113-119. https://doi.org/10.1002/net.20206

A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to fi... Read More about Transversals of subtree hypergraphs and the source location problem in digraphs.

Technology Supports for Distributed and Collaborative Learning over the Internet (2008)
Journal Article
Li, Q., Lau, R., Shih, T., & Li, F. (2008). Technology Supports for Distributed and Collaborative Learning over the Internet. ACM Transactions on Internet Technology, 8(2), Article 10. https://doi.org/10.1145/1323651.1323656

With the advent of Internet and World Wide Web (WWW) technologies, distance education (e-learning or Web-based learning) has enabled a new era of education. There are a number of issues that have significant impact on distance education, including th... Read More about Technology Supports for Distributed and Collaborative Learning over the Internet.

Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction (2008)
Journal Article
Krokhin, A., & Larose, B. (2008). Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM Journal on Discrete Mathematics, 22(1), 312-328. https://doi.org/10.1137/060669565

Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a superm... Read More about Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction.

Complexity of clausal constraints over chains (2008)
Journal Article
Creignou, N., Hermann, M., Krokhin, A., & Salzer, G. (2008). Complexity of clausal constraints over chains. Theory of Computing Systems, 42(2), 239-255. https://doi.org/10.1007/s00224-007-9003-z

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints b... Read More about Complexity of clausal constraints over chains.

A new algorithm for on-line coloring bipartite graphs (2008)
Journal Article
Broersma, H., Capponi, A., & Paulusma, D. (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics, 22(1), 72-91. https://doi.org/10.1137/060668675

We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs... Read More about A new algorithm for on-line coloring bipartite graphs.

Subdivision Surfaces and Applications (2008)
Book Chapter
Catalano, C., Ivrissimtzis, I., & Nasri, A. (2008). Subdivision Surfaces and Applications. In L. De Floriani, & M. Spagnuolo (Eds.), Shape analysis and structuring (115-143). Springer Verlag. https://doi.org/10.1007/978-3-540-33265-7_4

After a short introduction on the fundamentals of subdivision surfaces, the more advanced material of this chapter focuses on two main aspects. First, shape interrogation issues are discussed; in particular, artifacts, typical of subdivision surfaces... Read More about Subdivision Surfaces and Applications.

Dualities for constraint satisfaction problems (2008)
Book Chapter
Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5

In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the fo... Read More about Dualities for constraint satisfaction problems.

Point Set Denoising using a Variational Bayesian Method (2008)
Journal Article
Yoon, M., & Ivrissimtzis, I. (2008). Point Set Denoising using a Variational Bayesian Method. Jeongbo gwahaghoe nonmunji. keompyuting ui silje, 14(5), 527-531

For statistical modeling, the model parameters are usually estimated by maximizing a probability measure, such as the likelihood or the posterior. In contrast, a variational Bayesian method threats the parameters of the model as probability distribut... Read More about Point Set Denoising using a Variational Bayesian Method.

Computing sharp 2-factors in claw-free graphs (2008)
Presentation / Conference Contribution
Broersma, H. J., & Paulusma, D. (2008, December). Computing sharp 2-factors in claw-free graphs. Presented at 33th International Symposium on Mathematical Foundations of Computer Science, Toru´n, Poland

In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this... Read More about Computing sharp 2-factors in claw-free graphs.

Comparing universal covers in polynomial time (2008)
Presentation / Conference Contribution
Fiala, J., & Paulusma, D. (2008, December). Comparing universal covers in polynomial time. Presented at 3rd International Computer Science Symposium in Russia, Moscow, Russia

The universal cover T G of a connected graph G is the unique (possible infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. Universal covers have major applications in the area of distributed computing. It is w... Read More about Comparing universal covers in polynomial time.