Professor Gregory Gutin

  1. 2022
  2. E-pub ahead of print

    Valued Authorization Policy Existence Problem: Theory and Experiments

    Crampton, J., Eiben, E., Gutin, G., Karapetyan, D. & Majumdar, D., 21 Apr 2022, (E-pub ahead of print) In: ACM Transactions on Privacy and Security.

    Research output: Contribution to journalArticlepeer-review

  3. Published

    On d-panconnected tournaments with large semidegrees

    Darbinyan, S. & Gutin, G., 12 Apr 2022, In: Discrete Mathematics. 345, 8, 14 p., 112931.

    Research output: Contribution to journalArticlepeer-review

  4. Forthcoming

    Generalized Noise Role Mining

    Crampton, J., Eiben, E., Gutin, G., Karapetyan, D. & Majumdar, D., Apr 2022, (Accepted/In press).

    Research output: Contribution to conferencePaperpeer-review

  5. Forthcoming

    Perfect Forests in Graphs and Their Extensions

    Gutin, G. & Yeo, A., Apr 2022, (Accepted/In press) In: Journal of Graph Theory.

    Research output: Contribution to journalArticlepeer-review

  6. Forthcoming

    Iterative Message Passing Algorithm for Vertex-disjoint Shortest Paths

    Dai, G., Gutin, G., Zhang, X. & Zhang, Z., 18 Jan 2022, (Accepted/In press) In: IEEE Transactions on Information Theory.

    Research output: Contribution to journalArticlepeer-review

  7. 2021
  8. Forthcoming

    Convergence and Correctness of Belief Propagation for Weighted Min-Max Flow

    Dai, G., Guo, L., Gutin, G., Zhang, X. & Zhang, Z., 27 Dec 2021, (Accepted/In press) In: Discrete Applied Mathematics.

    Research output: Contribution to journalArticlepeer-review

  9. Published

    Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis

    Crampton, J., Gutin, G. & Majumdar, D., 19 Aug 2021, In: ACM Transactions on Privacy and Security. 24, 3, p. 1-22 22 p., 21.

    Research output: Contribution to journalArticlepeer-review

  10. Published

    Perfect Forests in Graphs and Their Extensions

    Gutin, G. & Yeo, A., 18 Aug 2021, 46th International Symposium on Mathematical Foundations of Computer Science: LIPIcs (Leibniz International Proceedings in Informatics). Schloss Dagstuhl –Leibniz Center for Informatics, p. 1-13 13 p. 54

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  11. E-pub ahead of print

    Kings in Multipartite Hypertournaments

    Ai, J., Gerke, S. & Gutin, G., 2 Aug 2021, (E-pub ahead of print) In: Journal of Graph Theory.

    Research output: Contribution to journalArticlepeer-review

  12. Published

    Strong Subgraph Connectivity of Digraphs: A Survey

    Sun, Y. & Gutin, G., 12 Jun 2021, In: Journal of Interconnection Networks. 21, 4, p. 2142004.1-2142004.16 16 p.

    Research output: Contribution to journalArticlepeer-review

  13. Published

    Valued Authorization Policy Existence Problem

    Crampton, J., Eiben, E., Gutin, G., Karapetyan, D. & Majumdar, D., May 2021, Proceedings of 26th ACM SACMAT. p. 83-94

    Research output: Chapter in Book/Report/Conference proceedingChapter

  14. E-pub ahead of print

    Parameterized Pre-coloring Extension and List Coloring Problems

    Gutin, G., Majumdar, D., Ordyniak, S. & Wahlström, M., 29 Mar 2021, (E-pub ahead of print) In: SIAM Journal on Discrete Mathematics. 35, 1, p. 575-596 22 p.

    Research output: Contribution to journalArticlepeer-review

  15. Published

    Strong subgraph connectivity of digraphs

    Sun, Y. & Gutin, G., 18 Mar 2021, In: Graphs and Combinatorics. 37, p. 951-970 20 p.

    Research output: Contribution to journalArticlepeer-review

  16. Published

    The Effect of Social Distancing on the Reach of an Epidemic in Social Network

    Gutin, G., Hirano, T., Hwang, S-H., Neary, P. & Toda, A. A., 3 Mar 2021, In: Journal of Economic Interaction and Coordination.

    Research output: Contribution to journalArticlepeer-review

  17. Published

    Proximity and Remoteness in Directed and Undirected Graphs

    Ai, J., Gerke, S., Gutin, G. & Mafunda, S., Mar 2021, In: Discrete Mathematics. 344, 3, 112252.

    Research output: Contribution to journalArticlepeer-review

  18. Published

    r-Simple k-Path and Related Problems Parameterized by k/r

    Gutin, G., Wahlström, M. & Zehavi, M., Jan 2021, In: ACM Transactions on Algorithms (TALG). 17, 1, p. 1-64 64 p., 10.

    Research output: Contribution to journalArticlepeer-review

  19. Published

    Hamiltonicity, Pancyclicity and Full Cycle Extendability in Multipartite Tournaments

    Zhang, Z., Zhang, X., Gutin, G. & Lou, D., 2021, In: Journal of Graph Theory. 97, 2, p. 171-191 21 p.

    Research output: Contribution to journalArticlepeer-review

  20. 2020
  21. Published

    Component Order Connectivity in Directed Graphs

    Bang-Jensen, J., Eiben, E., Gutin, G., Wahlström, M. & Yeo, A., 4 Dec 2020, Proceedings of IPEC 2020, LIPIcs . Vol. 180. p. 2:1-2:16 16 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  22. E-pub ahead of print

    Approximation algorithms for general cluster routing problem

    Zhang, X., Du, D., Gutin, G., Ming, Q. & Sun, J., 27 Aug 2020, (E-pub ahead of print) Computing and Combinatorics : 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings. Kim, D., Uma, R. N., Cai, Z. & Lee, D. H. (eds.). Springer, p. 472-483 12 p. (Lecture Notes in Computer Science; vol. 12273).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  23. E-pub ahead of print

    Uniqueness of DP-Nash Subgraphs and D-sets in Weighted Graphs of Netflix Games

    Gutin, G., Neary, P. & Yeo, A., 27 Aug 2020, (E-pub ahead of print) p. 360-371. 12 p.

    Research output: Contribution to conferencePaperpeer-review

  24. Published

    Constraint Branching in Workflow Satisfiability Problem

    Gutin, G. & Karapetyan, D., Jun 2020, SACMAT 2020: Symposium on Access Control Models and Technologies. p. 93-103 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  25. Published

    Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs

    Gutin, G. & Sun, Y., May 2020, In: Discrete Mathematics. 343, 5, p. 1-4 4 p., 111816.

    Research output: Contribution to journalArticlepeer-review

  26. E-pub ahead of print

    Proper orientation number of triangle-free bridgeless outerplanar graphs

    Ai, J., Gerke, S., Gutin, G., Shi, Y. & Taoqiu, Z., 20 Apr 2020, (E-pub ahead of print) In: Journal of Graph Theory. p. 1-11 11 p.

    Research output: Contribution to journalArticlepeer-review

  27. E-pub ahead of print

    Arc-disjoint Strong Spanning Subdigraphs of Semicomplete Compositions

    Bang-Jensen, J., Gutin, G. & Yeo, A., 13 Apr 2020, (E-pub ahead of print) In: Journal of Graph Theory.

    Research output: Contribution to journalArticlepeer-review

  28. Published

    Algorithms for Workflow Satisfiability Problem with User-independent Constraints

    Gutin, G. & Karapetyan, D., Mar 2020, In: International Journal of Graph Computing. 1, 1, p. 25-38 14 p.

    Research output: Contribution to journalArticlepeer-review

  29. Published

    Parameterized Pre-Coloring Extension and List Coloring Problems

    Gutin, G., Majumdar, D., Ordyniak, S. & Wahlström, M., 27 Feb 2020, LIPIcs, Proceedings of STACS 2020. Vol. 154. p. 1-18 18 p. 15

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  30. 2019
  31. Published

    Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints

    Karapetyan, D., Parkes, A., Gutin, G. & Gagarin, A., 5 Sep 2019, In: Journal of Artificial Intelligence Research. 66, p. 1-38 38 p.

    Research output: Contribution to journalArticlepeer-review

  32. E-pub ahead of print

    Parameterized Resiliency Problems

    Crampton, J., Gutin, G., Koutecky, M. & Watrigant, R., 7 Aug 2019, (E-pub ahead of print) In: Theoretical Computer Science. p. 1-14 14 p.

    Research output: Contribution to journalArticlepeer-review

  33. Published

    Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs

    Sun, Y., Gutin, G. & Ai, J., Aug 2019, In: Discrete Mathematics. 342, 8, p. 2297-2305 9 p.

    Research output: Contribution to journalArticlepeer-review

  34. Published

    Clustering without replication in combinatorial circuits

    Donovan, Z., Gutin, G., Mkrtchyan, V. & Subramani, K., Aug 2019, In: Journal of Combinatorial Optimization. 38, 2, p. 481-501 21 p.

    Research output: Contribution to journalArticlepeer-review

  35. Published

    Bounded and Approximate Strong Satisfiability in Workflows

    Crampton, J., Gutin, G. & Majumdar, D., 28 May 2019, Proceedings of ACM SACMAT 2019. ACM, p. 179-184 6 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  36. Published

    Path-contractions, edge deletions and connectivity preservation

    Gutin, Z., Ramanujan, M. S., Reidl, F. & Wahlstrom, M., May 2019, In: Journal of Computer and System Sciences. 101, p. 1-20 20 p.

    Research output: Contribution to journalArticlepeer-review

  37. E-pub ahead of print

    Alternative parameterizations of Metric Dimension

    Gutin, G., Ramanujan, M. S., Reidl, F. & Wahlstrom, M., 25 Jan 2019, (E-pub ahead of print) In: Theoretical Computer Science. p. 1-11 11 p.

    Research output: Contribution to journalArticlepeer-review

  38. Published

    On r-Simple k-Path and Related Problems Parameterized by k/r

    Gutin, G., Wahlstrom, M. & Zehavi, M., Jan 2019, Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, p. 1750-1769 20 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  39. 2018
  40. E-pub ahead of print

    Strong subgraph k‐connectivity

    Sun, Y., Gutin, G., Yeo, A. & Zhang, X., 28 Nov 2018, (E-pub ahead of print) In: Journal of Graph Theory. p. 1-14 14 p.

    Research output: Contribution to journalArticlepeer-review

  41. E-pub ahead of print

    The Authorization Policy Existence Problem

    Berge, P., Crampton, J., Gutin, G. & Watrigant, R., 28 Nov 2018, (E-pub ahead of print) In: IEEE Transactions on Dependable and Secure Computing. p. 1-12 12 p.

    Research output: Contribution to journalArticlepeer-review

  42. Published

    Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

    Gutin, G., Reidl, F., Wahlstrom, M. & Zehavi, M., Aug 2018, In: Journal of Computer and System Sciences. 95, p. 69-85 17 p.

    Research output: Contribution to journalArticlepeer-review

  43. Published

    k-distinct in- and out-branchings in digraphs

    Gutin, G., Reidl, F. & Wahlstrom, M., Aug 2018, In: Journal of Computer and System Sciences. 95, p. 86-97 13 p.

    Research output: Contribution to journalArticlepeer-review

  44. 2017
  45. Published

    Path-Contractions, Edge Deletions and Connectivity Preservation

    Gutin, G., Ramanujan, M. S., Reidl, F. & Wahlstrom, M., 3 Sep 2017, The 25th Annual European Symposium on Algorithms (ESA 2017). p. 1-13 13 p. 47. (LIPICS; vol. 87).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  46. Published

    Parameterized and Approximation Algorithms for the Load Coloring Problem

    Barbero, F., Gutin, G., Jones, M. & Sheng, B., Sep 2017, In: Algorithmica. 79, 1, p. 211–229 19 p.

    Research output: Contribution to journalArticlepeer-review

  47. Published

    Cryptographic enforcement of information flow policies without public information via tree partitions

    Crampton, J., Farley, N., Gutin, G., Jones, M. & Poettering, B., 24 Aug 2017, In: Journal of Computer Security. 25, 6, p. 511-535 25 p.

    Research output: Contribution to journalArticlepeer-review

  48. Published

    On the Satisfiability of Workflows with Release Points

    Crampton, J., Gutin, G. & Watrigant, R., Jun 2017, SACMAT '17 Abstracts: Proceedings of the 22nd ACM on Symposium on Access Control Models and Technologies. ACM, p. 207-217 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  49. E-pub ahead of print

    Parameterized Resiliency Problems via Integer Linear Programming

    Crampton, J., Gutin, G., Koutecky, M. & Watrigant, R., 14 Apr 2017, (E-pub ahead of print) CIAC 2017, 10th International Conference on Algorithms and Complexity May 26, 2017 - May 28, 2017. Springer, Vol. 10236. p. 164-176 13 p. (Lecture Notes in Computer Science; vol. 10236).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  50. Published

    Odd properly colored cycles in edge-colored graphs

    Gutin, G., Sheng, B. & Wahlstrom, M., Apr 2017, In: Discrete Mathematics. 340, 4, p. 817–821 5 p.

    Research output: Contribution to journalArticlepeer-review

  51. Published

    The bi-objective workflow satisfiability problem and workflow resiliency

    Crampton, J., Gutin, G., Karapetyan, D. & Watrigant, R., 16 Mar 2017, In: Journal of Computer Security. 25, 1, p. 83-115 33 p.

    Research output: Contribution to journalArticlepeer-review

  52. Published

    Parameterized complexity of the k-arc Chinese Postman Problem

    Gutin, G., Jones, M. & Sheng, B., Mar 2017, In: Journal of Computer and System Sciences. 84, p. 107–119 13 p.

    Research output: Contribution to journalArticlepeer-review

  53. Published

    Acyclicity in edge-colored graphs

    Gutin, G., Jones, M., Sheng, B., Wahlstrom, M. & Yeo, A., 6 Feb 2017, In: Discrete Mathematics. 340, 2, p. 1-8 8 p.

    Research output: Contribution to journalArticlepeer-review

  54. Published

    Rural Postman Parameterized by the Number of Components of Required Edges

    Gutin, G., Wahlström, M. & Yeo, A., Feb 2017, In: Journal of Computer and System Sciences. 83, 1, p. 121-131 11 p.

    Research output: Contribution to journalArticlepeer-review

  55. Published

    Chinese Postman Problem on edge-colored multigraphs

    Gutin, G., Jones, M., Sheng, B., Wahlstrom, M. & Yeo, A., 30 Jan 2017, In: Discrete Applied Mathematics. 217, Part 2, p. 196-202 7 p.

    Research output: Contribution to journalArticlepeer-review

  56. Published

    k-Distinct In- and Out-Branchings in Digraphs

    Gutin, G., Reidl, F. & Wahlstrom, M., 2017, 44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Dagstuhl, p. 1-13 13 p. (Leibniz International Proceedings in Informatics ; vol. 80).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  57. Published

    Parameterized Complexity of the Workflow Satisfiability Problem

    Cohen, D., Crampton, J., Gutin, Z. & Wahlstrom, M., 2017, Combinatorial Optimization and Graph Algorithms. Fukunaga, T. & Kawarabayashi, K. (eds.). Springer-Verlag, p. 101-120 20 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  58. 2016
  59. E-pub ahead of print

    The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

    Gutin, G., Jones, M. & Wahlstrom, M., 29 Nov 2016, (E-pub ahead of print) In: SIAM Journal on Discrete Mathematics. 30, 4, p. 2177-2205 29 p.

    Research output: Contribution to journalArticlepeer-review

  60. Published

    On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations

    Crampton, J., Gagarin, A., Gutin, G., Jones, M. & Wahlstrom, M., Oct 2016, In: ACM Transactions on Privacy and Security. 19, 3, p. 1-29 29 p., 8.

    Research output: Contribution to journalArticlepeer-review

  61. Published

    Algorithms for the workflow satisfiability problem engineered for counting constraints

    Cohen, D., Crampton, J., Gagarin, A., Gutin, G. & Jones, M., Jul 2016, In: Journal of Combinatorial Optimization. 32, 1, p. 3–24 22 p.

    Research output: Contribution to journalArticlepeer-review

  62. Published

    Note on Perfect Forests

    Gutin, G., Jul 2016, In: Journal of Graph Theory. 82, 3, p. 233-235 3 p.

    Research output: Contribution to journalArticlepeer-review

  63. E-pub ahead of print

    Note on Perfect Forests in Digraphs

    Gutin, G. & Yeo, A., 17 Jun 2016, (E-pub ahead of print) In: Journal of Graph Theory. 85, 2, p. 372-377 6 p.

    Research output: Contribution to journalArticlepeer-review

  64. Published

    Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths

    Barbero, F., Gutin, G., Jones, M., Sheng, B. & Yeo, A., Jun 2016, In: Information Processing Letters. 116, 6, p. 433–436 4 p.

    Research output: Contribution to journalArticlepeer-review

  65. Published

    Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis

    Gutin, G. & Wahlstrom, M., Mar 2016, In: Information Processing Letters. 116, 3, p. 223-226 4 p.

    Research output: Contribution to journalArticlepeer-review

  66. E-pub ahead of print

    Parameterized Traveling Salesman Problem: Beating the Average

    Gutin, G. & Patel, V., 4 Feb 2016, (E-pub ahead of print) In: SIAM Journal on Discrete Mathematics. 30, 1, p. 220-238 19 p.

    Research output: Contribution to journalArticlepeer-review

  67. E-pub ahead of print

    Cryptographic Enforcement of Information Flow Policies Without Public Information

    Crampton, J., Farley, N., Gutin, G., Jones, M. & Poettering, B., 9 Jan 2016, (E-pub ahead of print) 13th International Conference on Applied Cryptography and Network Security (ACNS 2015) . Malkin, T., Kolesnikov, V., Bishop Lewko, A. & Polychronakis, M. (eds.). p. 389-408 20 p. (Lecture Notes in Computer Science; vol. 9092).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  68. Published

    Parameterizations of Test Cover with Bounded Test Sizes

    Crowston, R., Gutin, G., Jones, M., Muciaccia, G. & Yeo, A., Jan 2016, In: Algorithmica. 74, 1, p. 367-384 18 p.

    Research output: Contribution to journalArticlepeer-review

  69. Published

    A Multivariate Approach for Checking Resiliency in Access Control

    Crampton, J., Gutin, G. & Watrigant, R., 2016, Algorithmic Aspects in Information and Management: AAIM 2016. Springer-Verlag, p. 173-184 12 p. (Lecture Notes in Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingChapter

  70. Forthcoming

    Resiliency Policies in Access Control Revisited

    Crampton, J., Gutin, G. & Watrigant, R., 2016, (Accepted/In press) Proceedings of 21st ACM Symposium on Access Control Models and Technologies (SACMAT 2016). ACM

    Research output: Chapter in Book/Report/Conference proceedingChapter

  71. 2015
  72. Published

    Parameterized and Approximation Algorithms for the Load Coloring Problem

    Barbero, F., Gutin, G., Jones, M. & Sheng, B., 9 Nov 2015, 10th International Symposium on Parameterized and Exact Computation. Schloss Dagstuhl –Leibniz Center for Informatics, p. 43-54 12 p. (LIPIcs).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  73. Forthcoming

    On the Workflow Satisfiability Problem with Class-Independent Constraints

    Crampton, J., Gagarin, A., Gutin, G. & Jones, M., 2015, (Accepted/In press) 10th International Symposium on Parameterized and Exact Computation. Schloss Dagstuhl –Leibniz Center for Informatics, (LIPIcs).

    Research output: Chapter in Book/Report/Conference proceedingChapter

  74. Forthcoming

    Optimal Constructions for Chain-based Cryptographic Enforcement of Information Flow Policies

    Crampton, J., Farley, N., Gutin, G. & Jones, M., 2015, (Accepted/In press) 29th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy: DBSec 2015. Springer-Verlag

    Research output: Chapter in Book/Report/Conference proceedingChapter

  75. Forthcoming

    Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints

    Karapetyan, D., Gagarin, A. & Gutin, G., 2015, (Accepted/In press) FAW 2015, Lecture Notes in Computer Science.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  76. Published

    Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

    Gutin, G., Kratsch, S. & Wahlström, M., 2015, In: Algorithmica. p. 1-20 20 p.

    Research output: Contribution to journalArticlepeer-review

  77. Published

    Structural Parameterizations of the Mixed Chinese Postman Problem

    Gutin, G., Jones, M. & Wahlstrom, M., 2015, 23rd Europ. Symp. Algorithms (ESA 2015). Springer-Verlag, Vol. 9294. p. 668-679 (Lect. Notes Comput. Sci.).

    Research output: Chapter in Book/Report/Conference proceedingChapter

  78. Published

    Valued Workflow Satisfiability Problem

    Crampton, J., Gutin, G. & Karapetyan, D., 2015, Proceedings of the 20th ACM Symposium on Access Control Models and Technologies. p. 3-13 11 p.

    Research output: Chapter in Book/Report/Conference proceedingChapter

  79. 2014
  80. Published

    Iterative Plan Construction for the Workflow Satisfiability Problem

    Cohen, D., Crampton, J., Gagarin, A., Gutin, G. & Jones, M., 21 Nov 2014, In: Journal of Artificial Intelligence Research. 51, p. 555-577 23 p.

    Research output: Contribution to journalArticlepeer-review

  81. Published

    Parameterized Complexity of the $k$-Arc Chinese Postman Problem

    Gutin, G., Jones, M. & Sheng, B., 6 Mar 2014, European Symposium on Algorithms 2014. Springer-Verlag, Vol. 8737. p. 530-541 (Lecture Notes in Computer Science; vol. 8737).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  82. Published

    Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints

    Cohen, D., Crampton, J., Gagarin, A., Gutin, G. & Jones, M., 2014, FAW 2014. (Lecture Notes in Computer Science; vol. 8497).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  83. Published

    Fixed-parameter tractability of satisfying beyond the number of variables

    Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S. & Yeo, A., 2014, In: Algorithmica. 68, p. 739-757

    Research output: Contribution to journalArticlepeer-review

  84. Published

    Parameterized Algorithms for Load Coloring Problem

    Gutin, G. & Jones, M., 2014, In: Information Processing Letters. 114

    Research output: Contribution to journalArticlepeer-review

  85. Published

    Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs

    Gutin, G., Jones, M., Sheng, B. & Wahlström, M., 2014, Proceedings of WG 2014.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  86. Published

    Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

    Gutin, G., Kratsch, S. & Wahlström, M., 2014, Proceedings of IPEC 2014.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  87. Published

    Satisfying More Than Half of a System of Linear Equations Over GF(2): A Multivariate Approach

    Crowston, R., Fellows, M., Gutin, G., Jones, M., Kim, E. J., Rosamond, F., Ruzsa, I. Z., Thomasse, S. & Yeo, A., 2014, In: Journal of Computer and System Sciences. 80, p. 687-696

    Research output: Contribution to journalArticlepeer-review

  88. 2013
  89. Published

    On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem

    Crampton, J., Gutin, G. & Yeo, A., Jun 2013, In: ACM Transactions on Information and System Security. 16, 1, 4.

    Research output: Contribution to journalArticlepeer-review

  90. Published

    (Non-)existence of Polynomial Kernels for the Test Cover Problem

    Gutin, G., Muciaccia, G. & Yeo, A., 2013, In: Information Processing Letters. 113, p. 123-126

    Research output: Contribution to journalArticlepeer-review

  91. Forthcoming

    A new bound for 3-satisfiable MaxSat and its algorithmic application

    Gutin, G., Jones, M., Scheder, D. & Yeo, A., 2013, (Accepted/In press) In: Information and Computation. 8 p.

    Research output: Contribution to journalArticlepeer-review

  92. Published

    Constraint Expressions and Workflow Satisability

    Crampton, J. & Gutin, G., 2013, 18th ACM SACMAT. p. 73-84

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  93. Published

    Fixed-Parameter Tractability of Workflow Satisability in the Presence of Seniority Constraints

    Crampton, J., Crowston, R., Gutin, G., Jones, M. & Ramanujan, M. S., 2013, FAW-AAIM 2013: Lecture Notes in Computer Science. Vol. 7924. p. 198-209

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  94. Published

    Maximum Balanced Subgraph Problem Parameterized Above Lower Bound

    Crowston, R., Gutin, G., Jones, M. & Muciaccia, G., 2013, In: Theoretical Computer Science. 513, p. 434-445

    Research output: Contribution to journalArticlepeer-review

  95. Forthcoming

    Parameterized Complexity of k-Chinese Postman Problem

    Gutin, G., Muciaccia, G. & Yeo, A., 2013, (Accepted/In press) In: Theoretical Computer Science.

    Research output: Contribution to journalArticlepeer-review

  96. Forthcoming

    Parameterized Complexity of MaxSat Above Average

    Crowston, R., Gutin, G., Jones, M., Raman, V. & Saurabh, S., 2013, (Accepted/In press) In: Theoretical Computer Science.

    Research output: Contribution to journalArticlepeer-review

  97. Published

    Parameterized Complexity of Satisfying Almost All Linear Equations over F_2

    Crowston, R., Gutin, G., Jones, M. & Yeo, A., 2013, In: Theory of Computing Systems. 52, p. 719-728

    Research output: Contribution to journalArticlepeer-review

  98. 2012
  99. Published

    An algorithm for finding input-output constrained convex sets in an acyclic digraph

    Gutin, G., Johnstone, A., Reddington, J., Scott, E. & Yeo, A., May 2012, In: Journal of Discrete Algorithms. 13, p. 47-58 12 p.

    Research output: Contribution to journalArticlepeer-review

  100. Published

    A New Lower Bound on the Maximum Number of Satisfied clauses in Max-SAT and its algorithmic applications.

    Crowston, R., Gutin, G., Jones, M. & Yeo, A., 2012, In: Algorithmica. doi: 10.1007/s00453-011-9550-1

    Research output: Contribution to journalArticlepeer-review

  101. Published

    All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Number of Variables

    Gutin, G., van Iersel, L., Mnich, M. & Yeo, A., 2012, In: Journal of Computer and System Sciences. 78, p. 151--163

    Research output: Contribution to journalArticlepeer-review

  102. Forthcoming

    Constraint satisfaction problems parameterized above or below tight bounds: a survey

    Gutin, G. & Yeo, A., 2012, (Accepted/In press) Fellows Festschrift. (Lecture Notes in Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  103. Published

    Directed Acyclic Subgraph Problem Parameterized above Poljak-Turzik Bound

    Crowston, R., Gutin, G. & Jones, M., 2012, FSTTCS 2012: LIPICS . Vol. 18. p. 400-411

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  104. Published

    Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

    Karapetyan, D. & Gutin, G., 2012, In: European Journal of Operational Research. 219, p. 234--251

    Research output: Contribution to journalArticlepeer-review

  105. Forthcoming

    Fixed-parameter tractability of satisfying beyond the number of variables

    Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S. & Yeo, A., 2012, (Accepted/In press) SAT 2012. (Lecture Notes in Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  106. Forthcoming

    Hypercontractive inequality for pseudo-boolean functions of bounded Fourier width

    Gutin, G. & Yeo, A., 2012, (Accepted/In press) In: Discrete Applied Mathematics. 6 p.

    Research output: Contribution to journalArticlepeer-review

  107. Published

    On the parameterized complexity of the workflow satisfiability problem

    Crampton, J., Gutin, G. & Yeo, A., 2012, CCS '12 Proceedings of the 2012 ACM conference on Computer and communications security. New York: ACM, p. 857-868

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  108. Published

    Parameterized Complexity of MaxSat Above Average

    Crowston, R., Gutin, G., Jones, M., Raman, V. & Saurabh, S., 2012, LATIN 2012: Lect. Notes Comput. Sci.. Springer-Verlag, Vol. 7256. p. 184--194

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  109. Published

    Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming

    Gutin, G., Kim, E. J., Soleimanfallah, A., Szeider, S. & Yeo, A., 2012, In: Algorithmica. doi: 10.1007/s00453-011-9548-8

    Research output: Contribution to journalArticlepeer-review

  110. Published

    Parameterized eulerian strong component arc deletion problem on tournaments

    Crowston, R., Gutin, G., Jones, M. & Yeo, A., 2012, In: Information Processing Letters. 112, p. 249--251

    Research output: Contribution to journalArticlepeer-review

  111. Published

    Parameterized Study of the Test Cover Problem

    Crowston, R., Gutin, G., Jones, M., Saurabh, S. & Yeo, A., 2012, MFCS 2012: Lecture Notes in Computer Science . Vol. 7464. p. 283-295

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

Previous 1 2 3 Next