Gregory Z. Gutin

According to our database1, Gregory Z. Gutin authored at least 198 papers between 1993 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
On r-Simple k-Path and Related Problems Parameterized by k/r.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials.
J. Comput. Syst. Sci., 2018

k-distinct in- and out-branchings in digraphs.
J. Comput. Syst. Sci., 2018

Acyclic Digraphs.
Proceedings of the Classes of Directed Graphs., 2018

Basic Terminology, Notation and Results.
Proceedings of the Classes of Directed Graphs., 2018

2017
Note on Perfect Forests in Digraphs.
Journal of Graph Theory, 2017

Rural postman parameterized by the number of components of required edges.
J. Comput. Syst. Sci., 2017

The bi-objective workflow satisfiability problem and workflow resiliency.
Journal of Computer Security, 2017

Cryptographic enforcement of information flow policies without public information via tree partitions.
Journal of Computer Security, 2017

Odd properly colored cycles in edge-colored graphs.
Discrete Mathematics, 2017

Acyclicity in edge-colored graphs.
Discrete Mathematics, 2017

Chinese Postman Problem on edge-colored multigraphs.
Discrete Applied Mathematics, 2017

On the Satisfiability of Workflows with Release Points.
Proceedings of the 22nd ACM on Symposium on Access Control Models and Technologies, 2017

k-Distinct In- and Out-Branchings in Digraphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Path-Contractions, Edge Deletions and Connectivity Preservation.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Parameterized Constraint Satisfaction Problems: a Survey.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

The Authorization Policy Existence Problem.
Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy, 2017

Parameterized Resiliency Problems via Integer Linear Programming.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016
Kernelization, Permutation CSPs Parameterized above Average.
Encyclopedia of Algorithms, 2016

Kernelization, Constraint Satisfaction Problems Parameterized above Average.
Encyclopedia of Algorithms, 2016

On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations.
ACM Trans. Priv. Secur., 2016

Parameterized Traveling Salesman Problem: Beating the Average.
SIAM J. Discrete Math., 2016

The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth.
SIAM J. Discrete Math., 2016

Note on Perfect Forests.
Journal of Graph Theory, 2016

Algorithms for the workflow satisfiability problem engineered for counting constraints.
J. Comb. Optim., 2016

Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis.
Inf. Process. Lett., 2016

Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths.
Inf. Process. Lett., 2016

Parameterizations of Test Cover with Bounded Test Sizes.
Algorithmica, 2016

Resiliency Policies in Access Control Revisited.
Proceedings of the 21st ACM on Symposium on Access Control Models and Technologies, 2016

A Multivariate Approach for Checking Resiliency in Access Control.
Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015
Guest Editorial: Special Issue on Parameterized and Exact Computation.
Algorithmica, 2015

Valued Workflow Satisfiability Problem.
Proceedings of the 20th ACM Symposium on Access Control Models and Technologies, 2015

On the Workflow Satisfiability Problem with Class-independent Constraints.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Parameterized and Approximation Algorithms for the Load Coloring Problem.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints.
Proceedings of the Frontiers in Algorithmics - 9th International Workshop, 2015

Structural Parameterizations of the Mixed Chinese Postman Problem.
Proceedings of the Algorithms - ESA 2015, 2015

Optimal Constructions for Chain-Based Cryptographic Enforcement of Information Flow Policies.
Proceedings of the Data and Applications Security and Privacy XXIX, 2015

Cryptographic Enforcement of Information Flow Policies Without Public Information.
Proceedings of the Applied Cryptography and Network Security, 2015

2014
Satisfying more than half of a system of linear equations over GF(2): A multivariate approach.
J. Comput. Syst. Sci., 2014

Iterative Plan Construction for the Workflow Satisfiability Problem.
J. Artif. Intell. Res., 2014

Parameterized algorithms for load coloring problem.
Inf. Process. Lett., 2014

Report on NII Shonan Meeting 2013-018.
Bulletin of the EATCS, 2014

Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints.
Proceedings of the Frontiers in Algorithmics - 8th International Workshop, 2014

Parameterized Complexity of the k-Arc Chinese Postman Problem.
Proceedings of the Algorithms - ESA 2014, 2014

2013
On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem.
ACM Trans. Inf. Syst. Secur., 2013

Parameterized complexity of k-Chinese Postman Problem.
Theor. Comput. Sci., 2013

Parameterized Complexity and the Understanding, Design, and Analysis of Heuristics (NII Shonan Meeting 2013-2).
NII Shonan Meet. Rep., 2013

Corrigendum. The Linear Arrangement Problem Parameterized Above Guaranteed Value.
Theory Comput. Syst., 2013

Parameterized Complexity of Satisfying Almost All Linear Equations over $\mathbb{F}_{2}$.
Theory Comput. Syst., 2013

(Non-)existence of polynomial kernels for the Test Cover problem.
Inf. Process. Lett., 2013

A new bound for 3-satisfiable MaxSat and its algorithmic application.
Inf. Comput., 2013

Constraint expressions and workflow satisfiability.
Proceedings of the 18th ACM Symposium on Access Control Models and Technologies, 2013

Maximum Balanced Subgraph Problem Parameterized above Lower Bound.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints.
Proceedings of the Frontiers in Algorithmics <i>and</i> Algorithmic Aspects in Information and Management, 2013

2012
Note on Large Subsets of Binary Vectors with Similar Distances.
SIAM J. Discrete Math., 2012

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables.
J. Comput. Syst. Sci., 2012

Parameterized Eulerian strong component arc deletion problem on tournaments.
Inf. Process. Lett., 2012

Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem.
European Journal of Operational Research, 2012

Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width.
Discrete Applied Mathematics, 2012

A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications.
Algorithmica, 2012

Fixed-Parameter Tractability of Satisfying beyond the Number of Variables.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

Parameterized Study of the Test Cover Problem.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Parameterized Complexity of MaxSat above Average.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

On the parameterized complexity of the workflow satisfiability problem.
Proceedings of the ACM Conference on Computer and Communications Security, 2012

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011
Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems.
Theor. Comput. Sci., 2011

Vertex Cover Problem Parameterized Above and Below Tight Bounds.
Theory Comput. Syst., 2011

Local search heuristics for the multidimensional assignment problem.
J. Heuristics, 2011

Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem.
European Journal of Operational Research, 2011

A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem.
Evolutionary Computation, 2011

Special Issue on Parameterized Complexity of Discrete Optimization.
Discrete Optimization, 2011

Solving MAX-r-SAT Above a Tight Lower Bound.
Algorithmica, 2011

Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application.
Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

2010
A memetic algorithm for the generalized traveling salesman problem.
Natural Computing, 2010

Betweenness parameterized above tight lower bound.
J. Comput. Syst. Sci., 2010

FPT algorithms and kernels for the Directed k-Leaf problem.
J. Comput. Syst. Sci., 2010

Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem.
J. Comput. Syst. Sci., 2010

Note on maximal bisection above tight lower bound.
Inf. Process. Lett., 2010

Note on Max Lin-2 above Average.
Inf. Process. Lett., 2010

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops.
Discrete Applied Mathematics, 2010

Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs.
Australasian J. Combinatorics, 2010

Systems of Linear Equations over F2 and Problems Parameterized above Average.
Proceedings of the Algorithm Theory, 2010

Solving MAX-r-SAT Above a Tight Lower Bound.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming.
Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Application.
Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables.
Proceedings of the Algorithms, 2010

2009
Traveling Salesman Problem.
Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

Domination Analysis in Combinatorial Optimization.
Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

Minimum leaf out-branching and related problems.
Theor. Comput. Sci., 2009

Spanning Directed Trees with Many Leaves.
SIAM J. Discrete Math., 2009

Convex Sets in Acyclic Digraphs.
Order, 2009

A selection of useful theoretical tools for the design and analysis of optimization heuristics.
Memetic Computing, 2009

Algorithms for generating convex sets in acyclic digraphs.
J. Discrete Algorithms, 2009

Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems.
Electronic Notes in Discrete Mathematics, 2009

On the number of connected convex subgraphs of a connected acyclic digraph.
Discrete Applied Mathematics, 2009

On complexity of Minimum Leaf Out-Branching problem.
Discrete Applied Mathematics, 2009

Generalized Traveling Salesman Problem Reduction Algorithms.
Algorithmic Operations Research, 2009

A Memetic Algorithm for the Multidimensional Assignment Problem.
Proceedings of the Engineering Stochastic Local Search Algorithms. Designing, 2009

A Probabilistic Approach to Problems Parameterized above or below Tight Bounds.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Better Than Optimal: Fast Identification of Custom Instruction Candidates.
Proceedings of the 12th IEEE International Conference on Computational Science and Engineering, 2009

Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem.
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

Properly Coloured Cycles and Paths: Results and Open Problems.
Proceedings of the Graph Theory, 2009

Local Search Heuristics for the Multidimensional Assignment Problem.
Proceedings of the Graph Theory, 2009

2008
Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs.
SIAM J. Discrete Math., 2008

A dichotomy for minimum cost graph homomorphisms.
Eur. J. Comb., 2008

Minimum cost homomorphisms to semicomplete multipartite digraphs.
Discrete Applied Mathematics, 2008

Some Parameterized Problems On Digraphs.
Comput. J., 2008

Note on edge-colored graphs and digraphs without properly colored cycles.
Australasian J. Combinatorics, 2008

An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Minimum Cost Homomorphism Dichotomy for Oriented Cycles.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

Minimum Leaf Out-Branching Problems.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007
Memetic Algorithm for the Generalized Asymmetric Traveling Salesman Problem.
Proceedings of the Nature Inspired Cooperative Strategies for Optimization (NICSO 2007), 2007

The Greedy Algorithm for the Symmetric TSP.
Algorithmic Operations Research, 2007

Parameterized Algorithms for Directed Maximum Leaf Problems.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Better Algorithms and Bounds for Directed Maximum Leaf Problems.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

2006
Characterization of edge-colored complete graphs with properly colored Hamilton paths.
Journal of Graph Theory, 2006

On n-partite Tournaments with Unique n-cycle.
Graphs and Combinatorics, 2006

Hamilton cycles in digraphs of unitary matrices.
Discrete Mathematics, 2006

The traveling salesman problem.
Discrete Optimization, 2006

Minimum cost and list homomorphisms to semicomplete digraphs.
Discrete Applied Mathematics, 2006

Domination analysis for minimum multiprocessor scheduling.
Discrete Applied Mathematics, 2006

Note on Upper Bounds for TSP Domination Number.
Algorithmic Operations Research, 2006

On-line bin Packing with Two Item Sizes.
Algorithmic Operations Research, 2006

Multipartite tournaments with small number of cycles.
Australasian J. Combinatorics, 2006

Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Fixed-Parameter Complexity of Minimum Profile Problems.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

The Linear Arrangement Problem Parameterized Above Guaranteed Value.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
Kernels in planar digraphs.
J. Comput. Syst. Sci., 2005

A problem of finding an acceptable variant in generalized project networks.
JAMDS, 2005

Further Extension of the TSP Assign Neighborhood.
J. Heuristics, 2005

Batched bin packing.
Discrete Optimization, 2005

Mediated digraphs and quantum nonlocality.
Discrete Applied Mathematics, 2005

Optimal On-Line Bin Packing with Two Item Sizes.
Proceedings of the Algorithms and Complexity in Durham 2005, 2005

Finding Cheapest Cycles in Vertex-weighted Quasi-transitive and Extended Semicomplete Digraphs.
Proceedings of the Algorithms and Complexity in Durham 2005, 2005

Level of Repair Analysis and Minimum Cost Homomorphisms of Graphs.
Proceedings of the Algorithmic Applications in Management, First International Conference, 2005

2004
On the number of quasi-kernels in digraphs.
Journal of Graph Theory, 2004

Algorithms with large domination ratio.
J. Algorithms, 2004

When n-cycles in n-partite tournaments are longest cycles.
Discrete Mathematics, 2004

When the greedy algorithm fails.
Discrete Optimization, 2004

Extracting pure network submatrices in linear programs using signed graphs.
Discrete Applied Mathematics, 2004

2003
Transformations of generalized ATSP into ATSP.
Oper. Res. Lett., 2003

Steiner type problems for digraphs that are locally semicomplete or extended semicomplete.
Journal of Graph Theory, 2003

Upper bounds on ATSP neighborhood size.
Discrete Applied Mathematics, 2003

Domination analysis of combinatorial optimization problems.
Discrete Applied Mathematics, 2003

Assignment problem based algorithms are impractical for the generalized TSP.
Australasian J. Combinatorics, 2003

2002
Anti-matroids.
Oper. Res. Lett., 2002

Almost Minimum Diameter Orientations of Semicomplete Multipartite and Extended Digraphs.
Graphs and Combinatorics, 2002

Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP.
Discrete Applied Mathematics, 2002

Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number.
Discrete Applied Mathematics, 2002

Orientations of digraphs almost preserving diameter.
Discrete Applied Mathematics, 2002

Digraphs - theory, algorithms and applications.
Springer, ISBN: 978-1-85233-611-0, 2002

2001
TSP tour domination and Hamilton cycle decompositions of regular digraphs.
Oper. Res. Lett., 2001

Solution of a Conjecture of Volkmann on the Number of Vertices in Longest Paths and Cycles of Strong Semicomplete Multipartite Digraphs.
Graphs and Combinatorics, 2001

Construction heuristics for the asymmetric TSP.
European Journal of Operational Research, 2001

Remarks on hamiltonian digraphs.
Australasian J. Combinatorics, 2001

2000
Kings in semicomplete multipartite digraphs.
Journal of Graph Theory, 2000

Quasi-Hamiltonicity: A Series of Necessary Conditions for a Digraph to Be Hamiltonian.
J. Comb. Theory, Ser. B, 2000

Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs.
Discrete Mathematics, 2000

On the Hajo's number of graphs.
Discrete Mathematics, 2000

Detecting Embedded Networks in LP Using GUB Structures and Independent Set Algorithms.
Comp. Opt. and Appl., 2000

1999
On the Complexity of Hamiltonian Path and Cycle Problems in Certain Classes of Digraphs.
Discrete Applied Mathematics, 1999

Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour.
Computers & OR, 1999

Exponential neighbourhood local search for the traveling salesman problem.
Computers & OR, 1999

Connected (g, f)-factors and supereulerian digraphs.
Ars Comb., 1999

Construction Heuristics and Domination Analysis for the Asymmetric TSP.
Proceedings of the Algorithm Engineering, 1999

1998
A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs.
Journal of Graph Theory, 1998

Generalizations of tournaments: A survey.
Journal of Graph Theory, 1998

Upper domination and upper irredundance perfect graphs.
Discrete Mathematics, 1998

Note on alternating directed cycles.
Discrete Mathematics, 1998

A note on the cardinality of certain classes of unlabeled multipartite tournaments.
Discrete Mathematics, 1998

Alternating cycles and trails in 2-edge-coloured complete multigraphs.
Discrete Mathematics, 1998

Properly Coloured Hamiltonian Paths in Edge-coloured Complete Graphs.
Discrete Applied Mathematics, 1998

1997
Properly colored Hamilton cycles in edge-colored complete graphs.
Random Struct. Algorithms, 1997

A classification of locally semicomplete digraphs.
Discrete Mathematics, 1997

Alternating cycles and paths in edge-coloured multigraphs: A survey.
Discrete Mathematics, 1997

Paths and cycles in extended and decomposable digraphs, .
Discrete Mathematics, 1997

Vertex heaviest paths and cycles in quasi-transitive digraphs.
Discrete Mathematics, 1997

Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments.
Combinatorics, Probability & Computing, 1997

1996
Sufficient conditions for a digraph to be Hamiltonian.
Journal of Graph Theory, 1996

On k-strong and k-cyclic digraphs.
Discrete Mathematics, 1996

A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian.
Discrete Mathematics, 1996

Ranking the Vertices of a Complete Multipartite Paired Comparison Digraph.
Discrete Applied Mathematics, 1996

An approximate algorithm for combinatorial optimization problems with two parameters.
Australasian J. Combinatorics, 1996

1995
Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey.
Journal of Graph Theory, 1995

Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs.
Discrete Mathematics, 1995

Weakly Hamiltonian-connected ordinary multipartite tournaments.
Discrete Mathematics, 1995

Maximizing Traveling Salesman Problem for Special Matrices.
Discrete Applied Mathematics, 1995

1994
Minimizing and maximizing the diameter in orientations of graphs.
Graphs and Combinatorics, 1994

Polynomial algorithms for finding paths and cycles in quasi-transitive digraphs.
Australasian J. Combinatorics, 1994

1993
Finding a Longest Path in a Complete Multipartite Digraph.
SIAM J. Discrete Math., 1993

On Cycles in Multipartite Tournaments.
J. Comb. Theory, Ser. B, 1993


  Loading...