Outputs (87)

The computational complexity of the parallel knock-out problem (2008)
Journal Article
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

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.

On the fixed-parameter tractability of parameterized model-checking problems (2008)
Journal Article
Stewart, I. (2008). On the fixed-parameter tractability of parameterized model-checking problems. Information Processing Letters, 106(1), 33-36. https://doi.org/10.1016/j.ipl.2007.09.009

In this note, we show, through the use of examples, how generic results for proving fixed-parameter tractability which apply to restricted classes of structures can sometimes be more widely applied.

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.

Lessons from a cross-domain investigation of empirical practices (2008)
Presentation / Conference Contribution
Budgen, D., Bailey, J., Turner, M., Kitchenham, B., Brereton, P., & Charters, S. (2008, June). Lessons from a cross-domain investigation of empirical practices. Presented at 12th International Conference on Evaluation and Assessment in Software Engineering, EASE 2008, Bari, Italy

Context: We are seeking the best ways to employ evidence-based practices in software engineering research and practice. Objectives: To help assess our guidelines for conducting systematic literature reviews we have investigated how other academic dis... Read More about Lessons from a cross-domain investigation of empirical practices.

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.