Skip to main content

Research Repository

Advanced Search

All Outputs (96)

An Obstacle Detection Method for Visually Impaired Persons by Ground Plane Removal Using Speeded-Up Robust Features and Gray Level Co-Occurrence Matrix (2018)
Journal Article
Jindal, A., Aggarwal, N., & Gupta, S. (2018). An Obstacle Detection Method for Visually Impaired Persons by Ground Plane Removal Using Speeded-Up Robust Features and Gray Level Co-Occurrence Matrix. Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications, 28(2), https://doi.org/10.1134/s1054661818020086

A linear-time algorithm for maximum-cardinality matching on cocomparability graphs (2018)
Journal Article
Mertzios, G., Nichterlein, A., & Niedermeier, R. (2018). A linear-time algorithm for maximum-cardinality matching on cocomparability graphs. SIAM Journal on Discrete Mathematics, 32(4), 2820-2835. https://doi.org/10.1137/17m1120920

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general $m$-edge and $n$-vertex graphs, it is well known to be solvable in $O(m\sqrt{n})$ time. We present a linear-time algorithm to f... Read More about A linear-time algorithm for maximum-cardinality matching on cocomparability graphs.

Surjective H-Colouring over reflexive digraphs (2018)
Journal Article
Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality,... Read More about Surjective H-Colouring over reflexive digraphs.

Hereditary graph classes: when the complexities of coloring and clique cover coincide (2018)
Journal Article
Blanché, A., Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory, 91(3), 267-289. https://doi.org/10.1002/jgt.22431

graph is (H1;H2)-free for a pair of graphs H1;H2 if it contains no induced subgraph isomorphic to H1 or H2. In 2001, Král’, Kratochvíl, Tuza, and Woeginger initiated a study into the complexity of Colouring for (H1;H2)-free graphs. Since then, others... Read More about Hereditary graph classes: when the complexities of coloring and clique cover coincide.

On the parameterized complexity of (k,s)-SAT (2018)
Journal Article
Paulusma, D., & Szeider, S. (2019). On the parameterized complexity of (k,s)-SAT. Information Processing Letters, 43, 34-36. https://doi.org/10.1016/j.ipl.2018.11.005

Let (k, s)-SAT be the k-SAT problem restricted to formulas in which each variable occurs in at most s clauses. It is well known that (3, 3)-SAT is trivial and (3, 4)-SAT is NP-complete. Answering a question posed by Iwama and Takaki (DMTCS 1997), Ber... Read More about On the parameterized complexity of (k,s)-SAT.

Automatic Musculoskeletal and Neurological Disorder Diagnosis With Relative Joint Displacement From Human Gait (2018)
Journal Article
Rueangsirarak, W., Zhang, J., Aslam, N., Ho, E. S., & Shum, H. P. (2018). Automatic Musculoskeletal and Neurological Disorder Diagnosis With Relative Joint Displacement From Human Gait. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 26(12), 2387-2396. https://doi.org/10.1109/tnsre.2018.2880871

Musculoskeletal and neurological disorders are common devastating companions of ageing, leading to a reduction in quality of life and increased mortality. Gait analysis is a popular method for diagnosing these disorders. However, manually analyzing t... Read More about Automatic Musculoskeletal and Neurological Disorder Diagnosis With Relative Joint Displacement From Human Gait.