Publications

Algorithms and Complexity

To search for phrases, use quotation marks: "climate change smith"
To search for combinations of words, separate them by "AND" or "+": climate + change + Smith
If you don't use either of the above, the search will run on ANY keyword.

2022

Abrishami T, Chudnovsky M, Dibek C, Thomassé S, Trotignon N, Vušković K. 2022. Graphs with polynomially many minimal separators. Journal of Combinatorial Theory, Series B. 248-280 152
Brettell N, Horsfield J, Munaro A, Paesani G, Paulusma D. 2022. Bounding the mim-width of hereditary graph classes. Journal of Graph Theory. 117-151 99.1
Brettell N, Horsfield J, Munaro A, Paulusma D. 2022. List k-colouring P-free graphs: A Mim-width perspective. Information Processing Letters. 106168-106168 173
Abrishami T, Alecu B, Chudnovsky M, Hajebi S, Spirkl S, Vušković K. 2022. Induced subgraphs and tree decompositions V. One neighbor in a hole.
Alecu B, Chudnovsky M, Vušković K. 2022. Induced subgraphs and tree decompositions V. Small components of big vertices.
Horsfield J, Preissmann M, Robin C, Sintiari NLD, Trotignon N, Vusković K. 2022. When all holes have the same length.

2021

Cooper C, Dyer M, Greenhill C. 2021. A Triangle Process on Regular Graphs. 32nd International Workshop, IWOCA 2021
Abrishami T, Chudnovsky M, Dibek C, Hajebi S, Rzążewski P, Spirkl S, Vušković K. 2021. Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree.
Abrishami T, Chudnovsky M, Dibek C, Vušković K. 2021. Submodular functions and perfect graphs.
Dyer M, Greenhill C, Kleer P, Ross J, Stougie L. 2021. Sampling hypergraphs with given degrees. Discrete Mathematics. 344.11
Dyer M, Greenhill C, Müller H. 2021. Counting independent sets in graphs with bounded bipartite pathwidth. Random Structures & Algorithms. 204-237 59.2
Dyer M, Heinrich M, Jerrum M, Müller H. 2021. Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. Combinatorics, Probability and Computing.
Dyer M, Jerrum M, Müller H, Vušković K. 2021. Counting Weighted Independent Sets beyond the Permanent. SIAM Journal on Discrete Mathematics. 1503-1524 35.2
Maffray F, Penev I, Vušković K. 2021. Coloring Rings. Journal of Graph Theory. 642-683 96.4
Radovanović M, Trotignon N, Vuskovic K. 2021. The (theta, wheel)-free graphs Part IV: Induced paths and cycles. Journal of Combinatorial Theory: Series B. 495-531 146
Vuskovic K, Horsfield J. 2021. Two classes of β-perfect graphs that do not necessarily have simplicial extremes. Discrete Mathematics. 344.7
Cook L, Horsfield J, Preissmann M, Robin C, Seymour P, Sintiari NLD, Trotignon N, Vušković K. 2021. Graphs with all holes the same length.

2020

Brettell N, Horsfield J, Munaro A, Paesani G, Paulusma D. 2020. Bounding the mim-width of hereditary graph classes. Leibniz International Proceedings in Informatics, LIPIcs
Govorov A, Cai JY, Dyer M. 2020. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Abrishami T, Chudnovsky M, Vušković K. 2020. Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree.
Cameron K, Vuskovic K. 2020. Hadwiger's Conjecture for some hereditary classes of graphs: a survey. Bulletin of the European Association for Theoretical Computer Science. 131
Diot E, Radovanović M, Trotignon N, Vušković K. 2020. The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs. Journal of Combinatorial Theory. Series B. 123-147 143
Dyer ME, Galanis A, Goldberg LA, Jerrum M, Vigoda E. 2020. Random Walks on Small World Networks. ACM Transactions on Algorithms. 16.3
Radovanović M, Trotignon N, Vušković K. 2020. The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring. Journal of Combinatorial Theory, Series B. 185-218 143
Radovanović M, Trotignon N, Vušković K. 2020. The (theta, wheel)-free graphs Part II: Structure theorem. Journal of Combinatorial Theory, Series B. 148-184 143

2019

Dyer M, Greenhill C, Müller H. 2019. Counting independent sets in graphs with bounded bipartite pathwidth. WG 2019
Boncompagni V, Penev I, Vušković K. 2019. Clique-cutsets beyond chordal graphs. Journal of Graph Theory. 192-246 91.2
Boncompagni V, Radovanović M, Vušković K. 2019. The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs. Journal of Graph Theory. 591-628 90.4
Chudnovsky M, Liu C-H, Schaudt O, Spirkl S, Trotignon N, Vušković K. 2019. Triangle-free graphs that do not contain an induced subdivision of K₄ are 3-colorable. Journal of Graph Theory. 67-95 92.2
Chudnovsky M, Thomassé S, Trotignon N, Vuskovic K. 2019. Maximum independent sets in (pyramid, even hole)-free graphs.. CoRR. abs/1912.11246
Cooper C, Dyer M, Greenhill C, Handley A. 2019. The flip Markov chain for connected regular graphs. Discrete Applied Mathematics. 56-79 254
Dyer J, Dyer M, Djemame K. 2019. Order-Preserving Encryption Using Approximate Common Divisors. Journal of Information Security and Applications. 49
Dyer J, Dyer M, Xu J. 2019. Practical homomorphic encryption over the integers for secure computation in the cloud. International Journal of Information Security. 549-579 18.5
Dyer M, Muller H. 2019. Counting Perfect Matchings and the Switch Chain. SIAM Journal on Discrete Mathematics. 1146-1174 33.3
Dyer M, Muller H. 2019. Quasimonotone graphs. Discrete Applied Mathematics.
Dyer M, Müller H. 2019. Counting Independent Sets in Cocomparability Graphs. Information Processing Letters. 31-36 144
Knust S, Shakhlevitch NV, Waldherr S, Weiß C. 2019. Shop Scheduling Problems with Pliable Jobs. Journal of Scheduling.

2018

Dyer M, Muller H. 2018. Quasimonotone Graphs. 44th International Workshop on Graph-Theoretic Concepts in Computer Science
Lei L, Kwan RSK, Lin Z, Copado-Mendez PJ. 2018. Station level refinement of train unit network flow schedules. ICCL 2017
Lin Z, Kwan RSK. 2018. Redundant Coupling/decoupling in Train Unit Scheduling Optimization. International Network Optimization Conference 2017
Wang Y, Liu R, Kwan RSK. 2018. Simultaneous Rerouting and Rescheduling on Rail Networks under Weather Impact. TRB 97th Annual Meeting
Copado-Mendez PJ, Lin Z, Kwan RSK. 2018. Train Units Scheduling Optimization.
Cameron K, Da Silva MVG, Huang S, Vuskovic K. 2018. Structure and algorithms for (cap, even hole)-free graphs. Discrete Mathematics. 463-473 341.2
Cooper C, Dyer M, Frieze A, Rivera N. 2018. Discordant Voting Processes on Finite Graphs. SIAM Journal on Discrete Mathematics. 2398-2420 32.4
Shioura A, Shakhlevich N, Strusevich VA. 2018. Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches. European Journal of Operational Research. 795-818 266.3
Shioura A, Shakhlevich NV, Strusevich VA. 2018. Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost. Journal of Global Optimization.
Shioura A, Shakhlevich NV, Strusevich VA, Primas B. 2018. Models and algorithms for energy-efficient scheduling with immediate start of jobs. Journal of Scheduling. 505-516 21.5

2017

Dyer M, Gärtner B, Megiddo N, Welzl E. 2017. Linear Programming. In: Handbook of Discrete and Computational Geometry, 3rd Edition. Third Edition.
Boncompagni V, Penev I, Vuskovic K. 2017. Clique cutsets beyond chordal graphs. IX Latin and American Algorithms, Graphs and Optimization Sympoisium
Copado-Mendez P, Lin Z, Kwan R. 2017. Size limited iterative method (SLIM) for train unit scheduling. 12th Metaheuristics International Conference
Dyer J, Dyer M, Xu J. 2017. Order-preserving encryption using approximate integer common divisors. ESORICS 2017 International Workshops, DPM 2017 and CBT 2017
Dyer J, Dyer M, Xu J. 2017. Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. 16th IMA International Conference on Cryptography and Coding (IMACC 2017)
Kwan RSK, Lin Z, Copado-Mendez PJ, Lei L. 2017. Multi-commodity flow and station logistics resolution for train unit scheduling. Multidisciplinary International Scheduling Conference (MISTA 2017)
Lin Z, Kwan R. 2017. Multicommodity Flow Problems with Commodity Compatibility Relations. The 12th International Conference Applied Mathematical Programming and Modelling – APMOD 2016
Adler I, Le NK, Muller H, Radovanovic M, Trotignon N, Vuskovic K. 2017. On rank-width of even-hole-free graphs. Discrete Mathematics and Theoretical Computer Science. 19.1
Dyer M, Jerrum M, Muller H. 2017. On the switch Markov chain for perfect matchings. Journal of the ACM. 64.2
Lin Z, Barrena E, Kwan RSK. 2017. Train unit scheduling guided by historic capacity provisions and passenger count surveys. Public Transport. 137-154 9.1-2
Shioura A, Shakhlevich NV, Strusevich VA. 2017. Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints. INFORMS Journal on Computing. 724-736 29.4
Thomasse S, Trotignon N, Vuskovic K. 2017. A polynomial Turing-kernel for weighted independent set in bull-free graphs. Algorithmica. 619-641 77.3
Trotignon N, Vuskovic K. 2017. On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. Journal of Graph Theory. 233-248 84.3
Weiß C, Waldherr S, Knust S, Chakhlevitch NV. 2017. Open Shop Scheduling with Synchronization. Journal of Scheduling. 557-581 20.6

2016 & previous

Brandstadt A, Kratsch D, Muller H. 2007. Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG2007.
Dyer ME, Frieze AM, Foulds LR. 1987. On the Strength of Connectivity of Random Subgraphs of the n-Cube. In: North-Holland Mathematics Studies.
Dyer ME, Megiddo N, Welz E. 2004. Linear programming. In: Goodman JE; O'Rourke J (eds.) Handbook of Discrete and Computational Geometry. 2.
Kwan RS. 2004. Bus and train driver scheduling. In: Leung JY-T (eds.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis.
Nash JM, Dew PM, Dyer ME. 1996. Scalable and portable computing using the WPRAM model.
NASH JM, DYER ME, DEW PM. 1995. Designing practical parallel algorithms for scalable message passing machines.
Abdullahi SD, Dyer ME, Proll LG. 2003. Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems. 4th International Conference, DMTCS 2003
Aronson J, Dyer ME, Frieze AM, Suen S. 1994. On the Greedy Heuristic for Matchings.. Proceedings of the 5th ACM/SIAM Symposium on Discrete Algorithms
Bordewich MJR, Dyer ME, Karpinski M. 2005. Path coupling using stopping times. Fundamentals of Computation Theory, 15th International Symposium, FCT2005
Bordewich MJR, Dyer ME, Karpinski M. 2006. Stopping times, metrics and approximate counting. Automata, Languages and Programming: 33rd International Colloquium, Proceedings
Borgs C, Chayes JT, Dyer ME, Tetali P. 2004. On the sampling problem for H-colorings on the hypercubic lattice. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 63
Brasel H, Shakhlevitch N. 2003. LiSA - fit for cooperative development. Sixth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'03)
Broersma H, Kloks T, Kratsch D, Muller H. 1998. A generalization of AT-free graphs and a generic algorithm for solving treewidth, minimum fill-In and vertex ranking. Graph-Theoretic Concepts in Computer Science - 29th International Workshop,WG'98. (1998)
Bubley R, Dyer ME. 1997. Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT.. SODA '97 Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms
Bubley R, Dyer ME. 1997. Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains.. 38th Annual Symposium on Foundations of Computer Science
Bubley R, Dyer ME. 1998. Faster Random Generation of Linear Extensions.. Ninth Annual ACM/SIAM Symposium on Discrete Algorithms
Bubley R, Dyer ME, Greenhill CS. 1998. Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing.. Ninth Annual ACM/SIAM Symposium on Discrete Algorithms
Bulatov AA, Dyer ME, Goldberg LA, Jerrum M. 2012. Log-supermodular functions, functional clones and counting CSPs.. 29th International Symposium on Theoretical Aspects of Computer Science
C. D. Cooper, M. E. Dyer, A. J. Handley. 2009. The flip markov chain and a randomising P2P protocol. Principles of Distributed Computing (PODC)
Chang MS, Muller H. 2001. On the tree-degree of graphs. Graph-Theoretic Concepts in Computer Science - 27th International Workshop (WG 2001)
Chen X, Dyer M, Goldberg LA, Jerrum M, Lu P, McQuillan C, Richerby D. 2013. The complexity of approximating conservative counting CSPs. 30th Symposium on Theoretical Aspects of Computer Science (STACS’13)
Cheng TCE, Shakhlevitch N. 2002. Minimizing nondecreasing separable objective functions for the unit-time open shop scheduling problem. Proceedings of the 8th International Workshop on Project Management and Scheduling (PMS'02)
Cheng TCE, Shakhlevitch N. 2004. Two-machine open shop scheduling problem with controllable processing times. Ninth International Workshop on Project Management and Scheduling (PMS'04)
Conforti M, Cornuéjols G, Kapoor A, Vuskovic K. 1994. Recognizing Balanced 0, +/- Matrices.. Proceedings of the fifth annual ACM-SIAM symposium on Discrete Algorithms
Conforti M, Cornuéjols G, Kapoor A, Vuskovic K. 1995. A Mickey-Mouse Decomposition Theorem.. Integer Programming and Combinatorial Optimization, 4th International IPCO Conference, 1995 Proceedings
Conforti M, Cornuéjols G, Kapoor A, Vuskovic K. 1997. Finding an Even Hole in a Graph.. 38th Annual Symposium on Foundations of Computer Science
Cooper C, Dyer M, Frieze A, Rivera N. 2016. Discordant voting processes on finite graphs. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Cooper C, Dyer M, Greenhill C, SIAM ACM. 2005. Sampling regular graphs and a peer-to-peer network (Extended Abstract). PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS
Cooper CD, Dyer ME, Greenhill CS. 2005. Sampling regular graphs and a peer-too-peer network. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms
Cooper CD, Dyer ME, Handley AJ. 2010. Networks of random cycles. Symposium on Discrete Algorithms (SODA)
Cornuejols G, Liu X, Vuskovic K. 2003. A polynomial algorithm for recognizing perfect graphs. 44th Symposium on Foundations of Computer Science (FOCS 2003)
Cryan ME, Dyer ME. 2002. A polynomial time algorithm to approximately count contingency tables when the number of rows is constant. 34th Annual ACM Symposium on the Theory of Computing (STOC 2002)
Cryan ME, Dyer ME, Goldberg LA, Jerrum MR, Martin R. 2002. Rapidly mixing Markov Chains for sampling contingency tables with a constant number of rows. 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002)
Cryan ME, Dyer ME, Muller H, Stougie L. 2003. Random walks on the vertices of transportation polytopes with constant number of sources. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 03)
Cryan ME, Dyer ME, Randall DS. 2005. Approximately counting integral flows and cell-bounded contingency tables. STOC'05: Proceedings of the 37th ACM Symposium on the Theory of Computing
Dabrowski K, Lozin V, Müller H, Rautenbach D. 2011. Parameterized algorithms for the independent set problem in some hereditary graph classes. Combinatorial Algorithms 21st International Workshop, IWOCA 2010, Revised Selected Papers
Dyer M, Mohanaraj V. 2011. Pairwise-interaction games. Automata, Languages and Programming
Dyer ME. 1992. A Class of Convex Programs with Applications to Computational Geometry.. Proceedings of the Eighth Annual ACM Symposium on Computational Geometry
Dyer ME. 1995. A Parallel Algorithm for Linear Programming in Fixed Dimension.. SCG '95 Proceedings of the eleventh annual symposium on Computational Geometry
Dyer ME. 2003. Approximate counting by dynamic programming. STOC'03: Proceedings of the 35th Annual ACM Symposium on Theory of Computing
Dyer ME, Frieze A. 2001. Randomly colouring graphs with lower bounds on girth and maximum degree. 42nd Annual Symposium on Foundations of Computer Science (FOCS'01)
Dyer ME, Frieze AM. 1986. Fast Solution of Some Random NP-Hard Problems. Foundations of Computer Science, 1986, 27th Annual Symposium
Dyer ME, Frieze AM. 1990. Probabilistic Analysis of the Generalised Assignment Problem.. Integer Programming and Combinatorial Optimization
Dyer ME, Frieze AM. 1992. Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm.. Integer Programming and Combinatorial Optimization
Dyer ME, Frieze AM, Hayes TP, Vigoda E. 2004. Randomly Coloring Constant Degree Graphs.. FOCS
Dyer ME, Frieze AM, Hayes TP, Vigoda E. 2004. Randomly coloring constant degree graphs. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
Dyer ME, Frieze AM, Jerrum M. 1994. Approximately Counting Hamilton Cycles in Dense Graphs.. Proceedings of the 5th ACM/SIAM Symposium on Discrete Algorithms
Dyer ME, Frieze AM, Jerrum M. 1999. On Counting Independent Sets in Sparse Graphs.. Fortieth Symposium on Foundation of Computer Science
Dyer ME, Frieze AM, Kannan R. 1989. A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing
Dyer ME, Goldberg LA, Greenhill CS, Jerrum M. 2000. On the relative complexity of approximate counting problems.. Approximation Algorithms for Combinatorial Optimization
Dyer ME, Goldberg LA, Greenhill CS, Jerrum M, Mitzenmacher M. 2000. An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms
Dyer ME, Goldberg LA, Jalsenius M, Richerby D. 2010. The complexity of approximating bounded-degree Boolean #CSP. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010)
Dyer ME, Goldberg LA, Jalsenius M, Richerby D. 2010. The Complexity of Approximating Bounded-Degree Boolean #CSP.. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010
Dyer ME, Goldberg LA, Jerrum MR. 2002. Counting and sampling H-colourings. Randomization and Approximation Techniques in Computer Science, 6th International Workshop (RANDOM 2002)
Dyer ME, Goldberg LA, Jerrum MR. 2006. Dobrushin conditions and systematic scan. Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques
Dyer ME, Goldberg LA, Paterson M. 2006. On Counting Homomorphisms to Directed Acyclic Graphs.. ICALP (1)
Dyer ME, Goldberg LA, Paterson M. 2006. On counting homomorphisms to directed acyclic graphs. Automata, Languages and Programming: 33rd International Colloquium ICALP 2006, Proceedings Part I
Dyer ME, Greenhill CS. 1998. A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables.. The 25th Annual EATCS International Colloquium on Automata, Languages and Programming
Dyer ME, Greenhill CS. 2000. The complexity of counting graph homomorphisms. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms
Dyer ME, Jerrum MR, Muller H. 2016. On the switch Markov chain for perfect matchings. Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
Dyer ME, Jerrum MR, Vigoda E. 2002. Rapidly mixing Markov Chains for dismantleable constraint graphs. Randomization and Approximation Techniques in Computer Science 6th International Workshop (RANDOM 2002)
Dyer ME, Jerrum MR, Vigoda E. 2004. Rapidly mixing Markov chains for dismantleable constraint graphs. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 63
Dyer ME, Mohanaraj V. 2011. Pairwise-interaction games. Automata, Languages and Programming 38th International Colloquium, ICALP 2011, Proceeding Part I
Dyer ME, Nash JM, Dew PM. 1995. An Optimal Randomized Planar Convex Hull Algorithm With Good Empirical Performance.. SPAA'95 - 7th Annual ACM Symposium on Parallel Algorithms and Architectures
Dyer ME, Proll LG. 1977. Vertex enumeration in convex polyhedra - a comparative computational study. Proceedings of the CP77 Combinatorial Programming Conference
Dyer ME, Richerby D. 2010. On the complexity of #CSP. 42nd ACM Symposium on Theory of Computing (STOC 2010)
Dyer ME, Richerby D. 2011. The #CSP Dichotomy is Decidable.. 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Dyer ME, Sinclair A, Jerrum MR, Weitz D. 2002. Mixing in time and space for lattice spin systems: a combinatorial view. Randomization and Approximation Techniques in Computer Science 6th International Workshop (RANDOM 2002)
Gaw JA, Rattadilok P, Kwan RS. 2004. Distributed choice function hyper-heuristics for timetabling and scheduling. PATAT 2004 - Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling
Grekioti A, Shakhlevich NV. 2014. Scheduling bag-of-tasks applications to optimize computation time and cost. 10th International Conference on Parallel Processing and Applied Mathematics (PPAM 2013)
Gudynas M, Kwan RS. 2009. Genetic and local search algorithms for train crew rostering. 11th International Conference on Advanced Systems for Public Transport (CASPT)
Indra-Payoong N, Kwan R, Proll L. 2003. Constraint-based local search for rail container service planning. MISTA 2003 Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications
Indra-Payoong N, Kwan R, Proll L. 2004. Demand responsive scheduling of rail container traffic. Proceedings of the 10th World Transport Research Conference
Indra-Payoong N, Kwan R, Proll L. 2005. Rail container service planning : a constraint-based approach. Multidisciplinary Scheduling: Theory and Applications
Indra-Payoong N, Kwan RS, Proll LG. 2004. An adaptively relaxed constraint satisfaction approach for a demand responsive freight rail timetabling problem. PATAT 2004 - Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling
Kloks AJJ, Lee CM, Liu J, Muller H. 2003. On the recognition of general partition graphs. Graph-Theoretic Concepts in Computer Science - 29th International Workshop,WG 2001
Kratsch D, Muller H, Todinca I. 2003. Feedback vertex set and longest induced path on AT-free graphs. Graph-Theoretic Concepts in Computer Science - 29th International Workshop,WG 2003
Kwan ASK, Kwan RS. 2009. Case studies of TrainTRACS under contrasting train crew scheduling scenarios. 11th International Conference on Advanced Systems for Public Transport (CASPT)
Kwan ASK, Parker ME, Kwan RS, Fores S, Proll LG, Wren A. 2003. Recent advancement in an established driver scheduling system. MISTA 2003 Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications
Kwan ASK, Parker ME, Kwan RS, Fores S, Proll LG, Wren A. 2004. Recent advances in TRACS. CASPT 2004 Proceedings
Kwan RS. 2009. Case studies of successful train crew scheduling. 4th Multidisciplinary International Conference on Scheduling : Theory and Applications
Kwan RS, Mistry P. 2003. A co-evolutionary algorithm for train timetabling. 2003 Congress on Evolutionary Computation
Kwan RS, Mistry P. 2003. A co-evolutionary approach for train timetabling. MISTA 2003 Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications
Laplagne IE, Kwan RS, Kwan ASK. 2004. A hybridised exact and local search method for robust train driver schedules planning. PATAT 2004 - Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling
Laplagne IE, Kwan RS, Kwan ASK. 2005. A hybridised integer programming and local search method for robust train driver schedules planning. Practice and Theory of Automated Timetabling V: 5th International Conference, PATAT 2004
Le VB, Mosca R, Muller H. 2005. On stable cutsets in claw-free graphs and planar graphs. Graph-Theoretic Concepts in Computer Science: 31st International Workshop, WG 2005
Li J, Kwan RS. 2001. Evolutionary driver scheduling with fuzzy evaluation. Proceedings of the Graduate Student Workshop at Genetic and Evolutionary Computation Conference
Li J, Kwan RS. 2001. A fuzzy simulated evolution algorithm for the driver scheduling problem. 2001 Congress on Evolutionary Computation (CEC2001)
Li J, Kwan RS. 2001. A fuzzy theory based evolutionary approach for driver scheduling. International conference on genetic algorithms; GECCO-2001 proceedings of the genetic and evolutionary computation conference
Li J, Kwan RS. 2002. A fuzzy evolutionary approach with Taguchi parameter setting for the set covering problem. Proceedings of the Congress on Evolutionary Computation, Honolulu, May 2002
Lin Z, Barrena E, Kwan RSK. 2015. Train unit scheduling with bi-level capacity requirements. Conference on Advanced Systems in Public Transport (CASPT 2015)
Lin Z, Kwan RS. 2012. A Two-phase Approach for Real-world Train Unit Scheduling. Conference on Advanced Systems for Public Transport (CASPT12)
McCollum B, Kwan RS, McMullan PJ. 2009. Real world optimisation through spin out activity. 4th Multidisciplinary International Conference on Scheduling : Theory and Applications
Mistry P, Kwan RS. 2003. Generation and optimization of train timetables using coevolution. Genetic and Evolutionary Computation - GECCO 2003
Muller H, Wilson S. 2013. An FPT certifying algorithm for the vertex-deletion problem. 24th International Workshop, IWOCA 2013
Müller H. 2012. On the stable degree of graphs. 38th International Workshop, WG 2012
Müller H, Wilson S. 2013. Characterising subclasses of perfect graphs with respect to partial orders related to edge contraction.. 12th Cologne-Twente Workshop on Graphs & Combinatorial Optimization
Nash JM, Dew PM, Davy JR, Dyer ME. 1996. Implementation Issues Relating to the WPRAM Model for Scalable Computing.. Euro-Par Parallel Processing, Vol. II
Primas B, Djemame K, Garraghan P, Shakhlevich N. 2016. Resource boxing: Converting realistic cloud task utilization patterns for theoretical scheduling. 9th IEEE/ACM International Conference on Utility and Cloud Computing, UCC 2016
Rattadilok P, Gaw A, Kwan RSK. 2005. Distributed choice function hyper-heuristics for timetabling and scheduling. Practice and Theory of Automated Timetabling V, 5th International Conference, PATAT 2004
Shakhlevich NV. 2013. Scheduling divisible loads to optimize the computation time and cost. 10th International Conference (GECON 2013)
Shakhlevich NV, Shioura A, Strusevich VA. 2008. Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times – a polymatroid optimization approach. Proceedings of the 16th Annual European Symposium on Algorithms (ESA 2008)
Shakhlevich NV, Shioura A, Strusevich VA. 2008. Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - A polymatroid optimization approach. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Shakhlevitch N. 2005. On some issues of inverse scheduling. Seventh Workshop on Models and Algorithms for Planning and Scheduling (MAPSP'05)
Shakhlevitch N, Strusevich VA. 2003. On two bicriteria scheduling problems with controllable processing times. Sixth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'03)
Shen Y, Kwan RS. 2001. A constructive approach to bus and train driver scheduling. Proceedings of the 10th Annual Industrial Engineering Research Conference
Shen Y, Kwan RS. 2001. Tabu search for driver scheduling. Computer-Aided Scheduling of Public Transport
Shioura A, Chakhlevitch NV, Strusevich VA. 2016. Handling Scheduling Problems with Controllable Parameters by Methods of Submodular Optimization. 9th International Conference, DOOR
Shioura A, Shakhlevich NV, Strusevich VA. 2015. Scheduling imprecise computations on parallel machines with linear and nonlinear error penalties. MAPS 2015
Shioura A, Shakhlevich NV, Strusevich VA. 2015. Energy optimization in speed scaling models via submodular optimization. MAPS 2015
SOTSKOV YN, SHAKHLEVICH NV, ENGINEERS IE, ENGINEERS IE, ENGINEERS IE. 1994. AN ADAPTIVE APPROACH IN PRODUCTION SCHEDULING BASED ON THE MIXED GRAPH MODEL. SECOND INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS ENGINEERING
Thomassé S, Trotignon N, Vušković K. 2014. A polynomial turing-Kernel for weighted independent set in bull-free graphs. Graph-Theoretic Concepts in Computer Science, 40th International Workshop, WG 2014, Revised Selected Papers
Vuskovic K. 2013. The world of hereditary graph classes viewed through Truemper configurations. 24th British Combinatorial Conference
Weiß C, Knust S, Shakhlevich NV, Waldherr S. 2015. On the assignment problem with a nearly Monge matrix and its applications in scheduling. MAPS 2015
Kwan R, Barrena E, Lin Z. 2015. CASPT2015: Train unit scheduling with bi-level capacity requirements.
Aboulker P, Charbit P, Trotignon N, Vuskovic K. 2015. Vertex elimination orderings for hereditary graph classes. Discrete Mathematics. 825-834 338.5
Aboulker P, Radovanovic M, Trotignon N, Trunck T, Vuskovic K. 2014. Linear Balanceable and Subcubic Balanceable Graphs. JOURNAL OF GRAPH THEORY. 150-166 75.2
Aboulker P, Radovanovic M, Trotignon N, Vuskovic K. 2013. Graphs that do not contain a cycle with a node that has at least two neighbors on it.. CoRR. abs/1309.1841
Aboulker P, Radovanović M, Trotignon N, Vušković K. 2012. Graphs that do not contain a cycle with a node that has at least two neighbors on it. SIAM Journal on Discrete Mathematics. 1510-1531 26.4
Abu-Khzam FN, Feghali C, Muller H. 2015. Partitioning a graph into disjoint cliques and a triangle-free graph. Discrete Applied Mathematics. 1-12 190-191
Aronson J, Dyer ME, Frieze AM, Suen S. 1995. Randomized Greedy Matching II.. Random Struct. Algorithms. 55-74 6
Babel L, Kloks AJJ, Kratochvil J, Kratsch D, Muller H, Olariu S. 2001. Efficient algorithms for graphs with few P4's. Discrete Mathematics. 29-51 235.1-3
Bordewich M, Dyer M, Karpinski M. 2008. Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Structures and Algorithms. 375-399 32.3
Bordewich M, Dyer ME, Karpinski M. 2005. Metric Construction, Stopping Times and Path Coupling.. Electron. Colloquium Comput. Complex..
Bordewich M, Dyer ME, Karpinski M. 2008. Path coupling using stopping times and counting independent sets and colorings in hypergraphs.. Random Struct. Algorithms. 375-399 32
Bordewich MJR, Dyer ME. 2007. Path coupling without contraction. Journal of Discrete Algorithms. 280-292 5
Bouchitte V, Kratsch D, Muller H, Todinca I. 2004. On treewidth approximations. Discrete Applied Mathematics. 183-196 136.2-3
Bouchitté V, Kratsch D, Müller H, Todinca I. 2001. On treewidth approximations. Electronic Notes in Discrete Mathematics. 1-4 8
Brasel H, Shakhlevich N. 1998. On the solution region for certain scheduling problems with preemption. ANNALS OF OPERATIONS RESEARCH. 1-21 83
Broder AZ, Dyer ME, Frieze AM, Raghavan P, Upfal E. 1995. The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.. Inf. Process. Lett.. 79-81 56
Broersma H, Kratsch D, Kloks AJJ, Muller H. 2002. A generalization of AT-free graphs and a generic algorithm for solving triangulation problems. Algorithmica. 594-610 32.4
Brucker P, Chakhlevitch NV. 2016. Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines. Journal of Scheduling. 659-685 19.6
Brucker P, Cheng TCE, Knust S, Shakhlevitch N. 2004. Complexity results for shop problems with transportation delays. Annals of Operations Research. 81-106 129
Brucker P, Knust S, Cheng TCE, Shakhlevich NV. 2004. Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays. Annals of Operations Research. 81-106 129.1-4
Brucker P, Shakhlevich NV. 2009. Inverse scheduling with maximum lateness objective. Journal of Scheduling. 475-488 12
Brucker P, Shakhlevich NV. 2011. Inverse scheduling: two machine flow shop problem. Journal of Scheduling. 239-256 14.3
Brucker P, Shakhlevich NV. 2011. A polynomial-time algorithm for a flow-shop batching problem with equal-length operations. Journal of Scheduling. 371-389 14.4
Bruns F, Knust S, Chakhlevitch N. 2016. Complexity results for storage loading problems with stacking constraints. European Journal of Operational Research. 1074-1081 249.3
Bubley R, Dyer ME. 1999. Faster random generation of linear extensions.. Discret. Math.. 81-88 201
Bubley R, Dyer ME, Greenhill CS, Jerrum M. 1999. On Approximately Counting Colorings of Small Degree Graphs.. SIAM J. Comput.. 387-400 29
Bubley R, Dyer ME, Jerrum M. 1998. An elementary analysis of a procedure for sampling points in a convex body.. Random Struct. Algorithms. 213-235 12
Bulaov AA, Dyer M, Goldberg LA, Jerrum M, McQuillan C. 2013. The Expressibility of Functions on the Boolean Domain, with Applications to Counting CSPs. Journal of the ACM. 60.5
Bulatov AA, Dyer ME, Goldberg LA, Jalsenius M, Jerrum M, Richerby D. 2012. The complexity of weighted and unweighted #CSP.. J. Comput. Syst. Sci.. 681-688 78
Bulatov AA, Dyer ME, Goldberg LA, Jalsenius M, Jerrum MR, Richerby D. 2012. The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences. 681-688 78.2
Bulatov AA, Dyer ME, Goldberg LA, Jalsenius M, Richerby D. 2009. The complexity of weighted Boolean #CSP with mixed signs. Theoretical Computer Science. 3949-3961 410
Bulatov AA, Dyer ME, Goldberg LA, Jalsenius M, Richerby D. 2009. The complexity of weighted Boolean #CSP with mixed signs.. Theor. Comput. Sci.. 3949-3961 410
Bulatov AA, Dyer ME, Goldberg LA, Jerrum M. 2011. Log-supermodular functions, functional clones and counting CSPs. CoRR. abs/1108.5288
Charbit P, Habib M, Trotignon N, Vušković K. 2012. Detecting 2-joins faster. Journal of Discrete Algorithms. 60-66 17
Charbit P, Habib M, Trotignon N, Vušković K. 2012. Detecting 2-joins faster. Journal of Discrete Algorithms. 60-66 17
Chen X, Dyer M, Goldberg LA, Jerrum M, Lu P, McQuillan C, Richerby D. 2015. The complexity of approximating conservative counting CSPs. Journal of Computer and System Sciences. 311-329 81.1
Cheng TCE, Chen ZL, Shakhlevitch N. 2002. Common due date assignment and scheduling with ready times. Computers & Operations Research. 1957-1967 29.14
Cheng TCE, Kovalyov MY, Shakhlevitch N. 2006. Scheduling with controllable release dates and processing times: Total completion time minimization. European Journal of Operational Research. 769-781+ 175
Cheng TCE, Kovalyov MY, Shakhlevitch N. 2006. Scheduling with controllable release dates and processing times: Makespan minimization. European Journal of Operational Research. 751-768 175.2
Cheng TCE, Shakhlevich N. 1999. Proportionate flow shop with controllable processing times. Journal of Scheduling. 253-265 2.6
Cheng TCE, Shakhlevitch N. 2003. Single machine scheduling of unit-time jobs with controllable release dates. Journal of Global Optimization. 293-311 27.2-3
Cheng TCE, Shakhlevitch N. 2005. Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem. European Journal of Operational Research. 444-456 165
Cheng TCE, Shakhlevitch N. 2007. Two-machine open shop problem with controllable processing times. Discrete Optimization. 175-184 4.2
Chudnovsky M, Cornuejols G, Liu X, Seymour P, Vuskovic K. 2005. Recognizing Berge graphs. Combinatorica. 143-186 25.2
Chudnovsky M, Lo I, Maffray F, Trotignon N, Vuskovic K. 2015. Coloring Square-free Berge Graphs. arXiv.
Chudnovsky M, Trotignon N, Trunck T, Vušković K. 2015. Coloring perfect graphs with no balanced skew-partitions. Journal of Combinatorial Theory. Series B. 26-65 115
Condotta A, Knust S, Meier D, Shakhlevich NV. 2012. Tabu search and lower bounds for a combined production-transportation problem. Computers and Operations Research. 886-900 40.3
Condotta A, Knust S, Shakhlevich NV. 2010. Parallel batch scheduling of equal-length jobs with release and due dates. Journal of Scheduling. 463-477 13
Condotta A, Knust S, Shakhlevich NV. 2010. Parallel batch scheduling of equal-length jobs with release and due dates. Journal of Scheduling. 463-477 13.5
Condotta A, Shakhlevich NV. 2012. Scheduling coupled-operation jobs with exact time-lags. Discrete Applied Mathematics. 2370-2388 160
Condotta A, Shakhlevich NV. 2014. Scheduling patient appointments via multilevel template: a case study in chemotherapy. Operations Research for Health Care. 129-144 3.3
Conforti M, Cornuejols G, Gasparyan G, Vuskovic K. 2002. Perfect graphs, partitionable graphs and cutsets. Combinatorica. 19-33 22.1
Conforti M, Cornuejols G, Kapoor A, Vuskovic K. 2001. Perfect, ideal and balanced matrices. European Journal of Operational Research. 455-461 133
Conforti M, Cornuejols G, Kapoor A, Vuskovic K. 2001. Balanced 0, ±1 Matrices II. Recognition Algorithm. Journal of Combinatorial Theory. Series B. 275-306 81.2
Conforti M, Cornuejols G, Kapoor A, Vuskovic K. 2001. Balanced 0, +/- 1 matrices I. Decomposition. J COMB THEORY B. 243-274 81.2
Conforti M, Cornuejols G, Kapoor A, Vuskovic K. 2002. Even-hole-free graphs, Part I: Decomposition Theorem. Journal of Graph Theory. 6-49 39.1
Conforti M, Cornuejols G, Kapoor A, Vuskovic K. 2002. Even-hole-free graphs part II: Recognition algorithm. Journal of Graph Theory. 238-266 40.4
Conforti M, Cornuejols G, Liu X, Vuskovic K, Zambelli G. 2006. Odd hole recognition in graphs of bounded clique size. SIAM Journal on Discrete Mathematics. 42-48 20.1
Conforti M, Cornuejols G, Vuskovic K. 2004. Square-free perfect graphs. Journal of Combinatorial Theory: Series B. 257-307 90.2
Conforti M, Cornuejols G, Vuskovic K. 2004. Decomposition of odd-hole-free graphs by double star cutsets and 2-joins. Discrete Applied Mathematics. 41-91 141.1-3
Conforti M, Cornuejols G, Vuskovic K. 2006. Balanced matrices. Discrete Applied Mathematics. 2411-2437 306.19-20
Conforti M, Cornuéjols G, Kapoor A, Vuskovic K. 1996. Perfect Matchings in Balanced Hypergraphs.. Comb.. 325-329 16
Conforti M, Cornuéjols G, Kapoor A, Vuskovic K. 1997. Universally Signable Graphs.. Comb.. 67-77 17
Conforti M, Cornuéjols G, Vuskovic K. 1999. Balanced cycles and holes in bipartite graphs.. Discret. Math.. 27-33 199
Cooper C, Dyer ME, Frieze AM, Rue R. 2000. Mixing properties of the Swendsen–Wang process on the complete graph and narrow grids. Journal of Mathematical Physics. 1499-1527 41.3
Cooper C, Dyer ME, Greenhill CS. 2007. Sampling regular graphs and a peer-to-peer network. Combinatorics, Probability and Computing. 557-593 16.4
Cooper C, Dyer ME, Mohanaraj V. 2011. On the Imitation Strategy for Games on Graphs. CoRR. abs/1102.3879
Cooper CD, Dyer ME, Frieze A. 2001. On Markov chains for randomly H-coloring a graph. Journal of Algorithms. 117-134 39.1
Cryan M, Dyer ME, Muller HHJ, Stougie L. 2008. Random walks on the vertices of transportation polytopes with constant number of sources. RANDOM STRUCT ALGOR. 333-355 33.3
Cryan ME, Dyer ME. 2003. A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. Journal of Computer and System Sciences. 291-310 67.2
da Silva MV, Vuskovic K. 2007. Triangulated neighborhoods in even-hole-free graphs. Discrete Mathematics. 1065-1073 307.9-10
da Silva MVG, Vušković K. 2013. Decomposition of even-hole-free graphs with star cutsets and 2-joins. Journal of Combinatorial Theory. Series B. 144-183 103
Dabrowski K, Lozin V, Müller H, Rautenbach D. 2012. Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. Journal of Discrete Algorithms. 207-213 14
de Figueiredo CMH, Klein S, Vuskovic K. 2002. The graph sandwich problem for 1-join composition is NP-complete. Discrete Applied Mathematics. 73-82 121.1-3
de Figueiredo CMH, Vuskovic K. 2001. Recognition of quasi-Meyniel graphs. Discrete Applied Mathematics. 255-260 113.2-3
Dyer M, Frieze A, Greenhill C. 2015. On the chromatic number of a random hypergraph. Journal of Combinatorial Theory, Series B. 68-122 113
Dyer M, Frieze A, Hayes TP, Vigoda E. 2013. Randomly Coloring Constant Degree Graphs. Random Structures and Algorithms. 181-200 43.2
DYER M, FRIEZE A, SUEN S. 1994. The Probability of Unique Solutions of Sequencing by Hybridization. Journal of Computational Biology. 105-110 1.2
DYER M, FRIEZE A, SUEN S. 1996. Corrigendum to Probability of Unique Solutions of Sequencing by Hybridization. Journal of Computational Biology. 331-331 3.2
Dyer M, Goldberg LA, Richerby D. 2016. Counting 4×4 matrix partitions of graphs. Discrete Applied Mathematics. 76-92 213
Dyer M, Goldberg LA, Richerby D, Jalsenius M. 2012. The complexity of approximating bounded-degree Boolean #CSP. Information and Computation. 1-14 220-221
Dyer M, Greenhill C. 2000. The complexity of counting graph homomorphisms. Random Structures and Algorithms. 260-289 17.3-4
Dyer M, Greenhill C. 2004. Erratum: The complexity of counting graph homomorphisms (Random Structures Algorithms (2000) 17 (260-289)). Random Structures and Algorithms. 346-352 25.3
Dyer M, Greenhill C, Ullrich M. 2014. Structure and eigenvalues of heat-bath Markov chains. Linear Algebra and Its Applications. 57-71 454
Dyer M, Jerrum M, Winkler P. 2004. Special issue on Isaac Newton Institute Programme - "Computation, combinatorics and probability": Part I - Preface. RANDOM STRUCTURES & ALGORITHMS. 233-233 24.3
Dyer M, Kannan R. 1997. On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension. Mathematics of Operations Research. 545-549 22.3
Dyer M, Kannan R, Stougie L. 2014. A simple randomised algorithm for convex optimisation: Application to two-stage stochastic programming. Mathematical Programming. 207-229 147.1-2
Dyer M, Potts C, Proll L. 1994. Preface. Discrete Applied Mathematics. 199-199 48.3
Dyer M, Richerby D. 2013. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing. 1245-1274 42.3
Dyer M, Stougie L. 2015. Erratum to: Computational complexity of stochastic programming problems. Mathematical Programming.
Dyer ME. 1980. Calculating surrogate constraints. Mathematical Programming. 255-278 19.1
Dyer ME. 1983. The Complexity of Vertex Enumeration Methods. Mathematics of Operations Research. 381-402 8.3
Dyer ME. 1984. Linear Time Algorithms for Two- and Three-Variable Linear Programs.. SIAM J. Comput.. 31-45 13
Dyer ME. 1984. An O(n) algorithm for the multiple-choice knapsack linear program. Mathematical Programming. 57-63 29.1
Dyer ME. 1986. On a Multidimensional Search Technique and its Application to the Euclidean One-Centre Problem.. SIAM J. Comput.. 725-738 15
Dyer ME. 1991. On Counting Lattice Points in Polyhedra.. SIAM J. Comput.. 695-707 20
Dyer ME. 1994. On a Universal Chain Problem.. Discret. Appl. Math.. 219-229 48
Dyer ME, Cryan M, Randall D. 2010. Approximately counting integral flows and cell-bounded contingency tables. SIAM Journal on Computing. 2683-2703 39.7
Dyer ME, Feige U, Frieze AM, Karpinski M. 2011. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).. Dagstuhl Reports. 24-53 1
Dyer ME, Fenner TI, Frieze AM, Thomason A. 1995. On Key Storage in Secure Networks.. J. Cryptol.. 189-200 8
Dyer ME, Flaxman A, Frieze A, Vigoda E. 2006. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures & Algorithms. 450-465 29
Dyer ME, Foulds LR, Frieze AM. 1985. Analysis of heuristics for finding a maximum weight planar subgraph. European Journal of Operational Research. 102-114 20.1
Dyer ME, Frieze A. 2003. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Structures & Algorithms. 167-179 23.2
Dyer ME, Frieze A, Jerrum MR. 2002. On counting independent sets in sparse graphs. SIAM Journal on Computing. 1527-1541 31.5
Dyer ME, Frieze AM. 1984. A Partitioning Algorithm for Minimum Weighted Euclidean Matching.. Inf. Process. Lett.. 59-62 18
Dyer ME, Frieze AM. 1985. A simple heuristic for the p-centre problem. Operations Research Letters. 285-288 3.6
Dyer ME, Frieze AM. 1985. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics. 139-153 10.2
Dyer ME, Frieze AM. 1986. Planar 3DM is NP-Complete.. J. Algorithms. 174-184 7
Dyer ME, Frieze AM. 1988. On the Complexity of Computing the Volume of a Polyhedron.. SIAM J. Comput.. 967-974 17
Dyer ME, Frieze AM. 1989. The Solution of Some Random NP-Hard Problems in Polynomial Expected Time.. J. Algorithms. 451-489 10
Dyer ME, Frieze AM. 1989. A randomized algorithm for fixed-dimensional linear programming. Mathematical Programming. 203-212 44.1-3
Dyer ME, Frieze AM. 1989. Randomized algorithm for fixed-dimensional linear programming. Mathematical Programming, Series A. 203-212 44.2
Dyer ME, Frieze AM. 1990. On Patching Algorithms for Random Asymmetric Travelling Salesman Problems.. Math. Program.. 361-378 46
Dyer ME, Frieze AM. 1990. On an optimization problem with nested constraints.. Discret. Appl. Math.. 159-173 26
Dyer ME, Frieze AM. 1991. Randomized Greedy Matching.. Random Struct. Algorithms. 29-46 2
Dyer ME, Frieze AM. 1991. Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph.. Random Struct. Algorithms. 233-240 2
Dyer ME, Frieze AM. 1992. Probabilistic analysis of the generalised assignment problem.. Math. Program.. 169-181 55
Dyer ME, Frieze AM. 1994. Random walks, totally unimodular matrices, and a randomised dual simplex algorithm.. Math. Program.. 1-16 64
Dyer ME, Frieze AM. 2010. Randomly coloring random graphs. Random Structures and Algorithms. 251-272 36.3
Dyer ME, Frieze AM, Jerrum M. 1998. Approximately Counting Hamilton Paths and Cycles in Dense Graphs.. SIAM J. Comput.. 1262-1272 27
Dyer ME, Frieze AM, Kannan R. 1991. A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.. J. ACM. 1-17 38
Dyer ME, Frieze AM, Kannan R, Kapoor A, Perkovic L, Vazirani UV. 1993. A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.. Comb. Probab. Comput.. 271-284 2
Dyer ME, Frieze AM, Mcdiarmid CJH. 1986. On linear programs with random costs. Mathematical Programming. 3-16 35.1
Dyer ME, Frieze AM, McDiarmid CJH. 1984. Partitioning heuristics for two geometric maximization problems. Operations Research Letters. 267-270 3.5
Dyer ME, Frieze AM, Molloy M. 2003. A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theoretical Computer Science. 1815-1828 290
Dyer ME, Frieze AM, Suen S. 1995. Ordering Clone Libraries in Computational Biology.. J. Comput. Biol.. 207-218 2
Dyer ME, Füredi Z, McDiarmid C. 1992. Volumes Spanned by Random Points in the Hypercube.. Random Struct. Algorithms. 91-106 3
Dyer ME, Goldberg LA. 2007. On counting homomorphisms to directed acyclic graphs. Journal of the ACM. 54
Dyer ME, Goldberg LA, Greenhill CS, Istrate G, Jerrum MR. 2002. Convergence of the iterated prisoner's dilemma game. Combinatorics, Probability and Computing. 135-148 11.2
Dyer ME, Goldberg LA, Greenhill CS, Jerrum MR. 2003. The relative complexity of approximate counting problems. Algorithmica. 471-500 38.3
Dyer ME, Goldberg LA, Greenhill CS, Jerrum MR, Mitzenmacher M. 2001. An extension of path coupling and its application to the Glauber dynamics for graph colorings. SIAM Journal on Computing. 1962-1975 30.6
Dyer ME, Goldberg LA, Jalsenius M, Richerby D. 2010. The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract). CoRR. abs/1001.4987
Dyer ME, Goldberg LA, Jerrum M. 2007. The Complexity of Weighted Boolean #CSP. CoRR. abs/0704.3683
Dyer ME, Goldberg LA, Jerrum M. 2008. Dobrushin Conditions and Systematic Scan.. Comb. Probab. Comput.. 761-779 17
Dyer ME, Goldberg LA, Jerrum M. 2008. A complexity dichotomy for hypergraph partition functions. CoRR. abs/0811.0037
Dyer ME, Goldberg LA, Jerrum M. 2010. An approximation trichotomy for Boolean #CSP.. J. Comput. Syst. Sci.. 267-277 76
Dyer ME, Goldberg LA, Jerrum MR. 2004. Counting and sampling H-colourings. Information and Computation. 1-16 189.1
Dyer ME, Goldberg LA, Jerrum MR. 2006. Systematic scan for sampling colorings. Annals of Applied Probability. 185-230 16
Dyer ME, Goldberg LA, Jerrum MR. 2008. Dobrushin conditions and systematic scan. Combinatorics, Probability & Computing. 761-779 17.6
Dyer ME, Goldberg LA, Jerrum MR. 2009. Matrix norms and rapid mixing for spin systems. The Annals of Applied Probability. 71-107 19
Dyer ME, Goldberg LA, Jerrum MR. 2009. The complexity of weighted Boolean #CSP. SIAM Journal on Computing. 1970-1986 38.5
Dyer ME, Goldberg LA, Jerrum MR. 2010. A Complexity Dichotomy For Hypergraph Partition Functions. Computational Complexity. 605-633 19.4
Dyer ME, Goldberg LA, Jerrum MR. 2010. An approximation trichotomy for Boolean #CSP. Journal of Computer and System Sciences. 267-277 76
Dyer ME, Goldberg LA, Jerrum MR, Martin R. 2006. Markov chain comparison. Probability Surveys. 89-111 3
Dyer ME, Greenhill CS. 1998. A more rapidly mixing Markov chain for graph colorings.. Random Struct. Algorithms. 285-317 13
Dyer ME, Greenhill CS. 2000. Polynomial-time counting and sampling of two-rowed contingency tables.. Theor. Comput. Sci.. 265-278 246
Dyer ME, Greenhill CS. 2000. On Markov Chains for Independent Sets.. J. Algorithms. 17-49 35
Dyer ME, Greenhill CS. 2000. The complexity of counting graph homomorphisms.. Random Struct. Algorithms. 260-289 17
Dyer ME, Greenhill CS, Molloy M. 2002. Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs. Random Structures & Algorithms. 98-114 20.1
Dyer ME, Gritzmann P, Hufnagel A. 1998. On the Complexity of Computing Mixed Volumes.. SIAM J. Comput.. 356-400 27
Dyer ME, Kannan R, Mount J. 1997. Sampling contingency tables.. Random Struct. Algorithms. 487-506 10
Dyer ME, Kayal N, Walker J. 1984. A branch and bound algorithm for solving the multiple-choice knapsack problem. Journal of Computational and Applied Mathematics. 231-249 11.2
Dyer ME, Mohanaraj V. 2011. The Iterated Prisoner's Dilemma on a Cycle. CoRR. abs/1102.3822
Dyer ME, Muller H. 2015. Graph classes and the switch Markov chain for matchings. Annales de la Faculte des Sciences de Toulouse Miclo L (eds.). 885-993 24.4
Dyer ME, Proll LG. 1977. An algorithm for determining all extreme points of a convex polytope. Mathematical Programming. 81-96 12
Dyer ME, Proll LG. 1977. On the validity of marginal analysis for allocating servers in M/M/c queues. Management Science. 1019-1022 23
Dyer ME, Proll LG. 1980. Eliminating extraneous edges in Greenberg's algorithm. Mathematical Programming. 106-110 19
Dyer ME, Proll LG. 1982. An improved vertex enumeration algorithm. European Journal of Operational Research. 359-368 9
Dyer ME, Richerby D. 2010. The Complexity of #CSP. CoRR. abs/1003.3879
Dyer ME, Riha WO, Walker J. 1995. A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice knapsack problem. Journal of Computational and Applied Mathematics. 43-54 58.1
Dyer ME, Sen S. 2000. Fast and optimal parallel multidimensional search in prams with applications to linear programming and related problems. SIAM J COMPUT. 1443-1461 30.5
Dyer ME, Sinclair A, Vigoda E, Weitz D. 2004. Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures & Algorithms. 461-479 24.4
Dyer ME, Stougie L. 2006. Computational complexity of stochastic programming problems. Mathematical Programming. 423-432 106
Dyer ME, Walker J. 1982. Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints. Mathematical Programming. 107-112 24.1
Dyer ME, Walker J. 1983. A note on bicriterion programming. Mathematical Programming. 355-361 27.3
Dyer ME, Walker J. 1987. An algorithm for a separable integer programming problem with cumulatively bounded variables. Discrete Applied Mathematics. 135-149 16.2
Dyer ME, Walker J. 1998. Dominance in multi-dimensional multiple-choice knapsack problems. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH. 159-168 15.2
Dyer ME, Wolsey LA. 1990. Formulating the single machine sequencing problem with release dates as a mixed integer program.. Discret. Appl. Math.. 255-270 26
Figueiredo CMHD, Klein S, Vuskovic K. 2000. The graph sandwich problem for 1-join composition is NP-complete.. Electron. Notes Discret. Math.. 89-92 5
Figueiredo CMHD, Vuskovic K. 2000. A class of ?-perfect graphs.. Discret. Math.. 169-193 216
Fomin FV, Kratsch D, Muller H. 2003. On the domination search number. Discrete Applied Mathematics. 565-580 127.3
Fomin FV, Kratsch D, Muller H. 2004. Algorithms for graphs with small octopus. Discrete Applied Mathematics. 105-128 134.1-3
Glass CA, Shakhlevich NV. 2013. Minimising the number of gap-zeros in binary matrices. European Journal of Operational Research. 45-58 229.1
Kloks AJJ, Kratochvil J, Muller H. 2005. Computing the branchwidth of interval graphs. Discrete Applied Mathematics. 266-275 145.2
Kloks AJJ, Kratsch D, Muller H. 2001. On the structure of graphs with bounded asteroidal number. Graphs and Combinatorics. 295-306 17.2
Kloks T, Muller H, Vuskovic K. 2009. Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences. Journal of Combinatorial Theory: Series B. 733-800 99.5
Kratsch D, Le HO, Muller H, Prisner E, Wagner D. 2003. Additive tree spanners. SIAM Journal on Discrete Mathematics. 332-340 17.2
Kratsch D, Muller H. 2009. On a property of minimal triangulations. DISCRETE MATH. 1724-1729 309.6
Kratsch D, Muller H, Todinca I. 2008. Feedback vertex set on AT-free graphs. DISCRETE APPL MATH. 1936-1947 156.10
Krüger K, Shakhlevich NV, Sotskov YN, Werner F. 1995. A heuristic decomposition algorithm for scheduling problems on mixed graphs. Journal of the Operational Research Society. 1481-1497 46.12
Kwan RS. 2011. Case studies of successful train crew scheduling optimization. Journal of Scheduling. 423-434 14.5
Kwan RS, Kwan ASK. 2007. Effective search space control for large and/or complex driver scheduling problems. Annals of Operations Research. 417-435 155.1
Kwan RS, Kwan ASK, Wren A. 2001. Evolutionary driver scheduling with relief chains. Evolutionary Computation. 445-460 9.4
Laplagne I, Kwan R, Kwan A. 2009. Critical time windowed train driver relief opportunities. Public Transport. 73-85 1
Le HO, Le VB, Muller H. 2003. Splitting a graph into disjoint induced paths or cycles. Discrete Applied Mathematics. 199-212 131.1
Le VB, Mosca R, Muller H. 2008. On stable cutsets in claw-free graphs and planar graphs. Journal of Discrete Algorithms. 256-276 6
Li J, Kwan RS. 2003. A fuzzy genetic algorithm for driver scheduling. European Journal of Operational Research. 334-344 147.2
Li J, Kwan RS. 2004. A meta-heuristic with orthogonal experiment for the set covering problem. Journal of Mathematical Modelling and Algorithms. 263-283 3.3
Li J, Kwan RS. 2005. A self-adjusting algorithm for driver scheduling. Journal of Heuristics. 351-367 11.4
Li SS, Brucker P, Ng CT, Shakhlevich NV, Yuan JJ. 2013. A note on reverse scheduling with maximum lateness objective. Journal of Scheduling. 417-422 16
Lin Z, Kwan RSK. 2013. An integer fixed-charge multicommodity flow (FCMF) model for train unit scheduling. Electronic Notes in Discrete Mathematics. 165-172 41
Lin Z, Kwan RSK. 2014. A two-phase approach for real-world train unit scheduling. Public Transport. 35-65 6.1-2
Lin Z, Kwan RSK. 2016. Local convex hulls for a special class of integer multicommodity flow problems. Computational Optimization and Applications. 881-919 64.3
Lin Z, Kwan RSK. 2016. A branch-and-price approach for solving the train unit scheduling problem. Transportation Research Part B: Methodological. 97-120 94
Machado RCS, de Figueiredo CMH, Vuskovic K. 2010. Chromatic index of graphs with no cycle with a unique chord. Theoretical Computer Science. 1221-1234 411.7-9
Maffray F, Trotignon N, Vuskovic K. 2013. Algorithms for square-$3PC(\cdot, \cdot)$-free Berge graphs.. CoRR. abs/1309.0694
Maffray F, Trotignon N, Vušković K. 2005. Algorithms for 3PC(.,.)-free Berge graphs. Electronic Notes in Discrete Mathematics. 73-77 22
Maffrey F, Trotignon N, Vuskovic K. 2008. Algorithms for square-3PC($\cdot, \cdot$)-free Berge graphs. SIAM Journal on Discrete Mathematics. 51-71 22.1
Muller H. 1996. On edge perfectness and classes of bipartite graphs. Discrete Mathematics. 159-187 149
Muller H. 1997. Recognizing interval digraphs and interval bigraphs in polynomial time. Discrete Applied Mathematics. 189-205 78
Muller H, Urner R. 2010. On a disparity between relative cliquewidth and relative NLC-width. DISCRETE APPL MATH. 828-840 158.7
Nash JM, Dew PM, Dyer ME. 1996. A Scalable Shared Queue on a Distributed Memory Machine.. Comput. J.. 483-495 39
Nash JM, Dew PM, Dyer ME. 1996. A scalable shared queue on a distributed memory machine. Computer Journal. 39.6
Radovanović M, Vušković K. 2012. A class of three-colorable triangle-free graphs. Journal of Graph Theory. 430-439 72.4
Shakhlevich N, Hoogeveen H, Pinedo M. 1998. Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling. 157-168 1.3
Shakhlevich NV. 2005. Open shop unit-time scheduling problems with symmetric objective functions. 4OR. 117-131 3.2
Shakhlevich NV, Shioura A, Strusevich VA. 2009. Single machine scheduling with controllable processing times by submodular optimization. International Journal of Foundations of Computer Science. 247-269 20
Shakhlevich NV, Sotskov YN. 1994. Scheduling two jobs with fixed and nonfixed routes. Computing. 17-30 52.1
Shakhlevich NV, Sotskov YN, Werner F. 1996. Adaptive scheduling algorithm based on mixed graph model. IEE Proceedings - Control Theory and Applications. 9-16 143.1
Shakhlevich NV, Sotskov YN, Werner F. 1999. Shop-scheduling problems with fixed and non-fixed machine orders of the jobs. ANNALS OF OPERATIONS RESEARCH. 281-304 92
Shakhlevich NV, Sotskov YN, Werner F. 2000. Complexity of mixed shop scheduling problems: A survey. European Journal of Operational Research. 343-351 120.2
Shakhlevich NV, Strusevich VA. 1993. Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function. European Journal of Operational Research. 391-404 70.3
Shakhlevich NV, Strusevich VA. 2008. Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica. 451-473 51
Shakhlevitch N. 2005. Unit-time open-shop scheduling problems with symmetric objective functions. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 117-131 3
Shakhlevitch N, Strusevich VA. 2005. Pre-emptive scheduling problems with controllable processing times. Journal of Scheduling. 233-253 8.3
Shakhlevitch N, Strusevich VA. 2006. Single machine scheduling with controllable release and processing parameters. Discrete Applied Mathematics. 2178-2199 154.15
Shioura A, Shakhlevitch N, Strusevich VA. 2015. Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Mathematical Programming. 495-534 153.2
Shioura A, Shakhlevitch N, Strusevich VA. 2016. Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines. Informs Journal on Computing. 148-161 28.1
Shioura A, Strusevich VA, Shakhlevich NV. 2013. A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM Journal on Discrete Mathematics. 186-204 27.1
Smith BM, Dyer ME. 1996. Locating the Phase Transition in Binary Constraint Satisfaction Problems.. Artif. Intell.. 155-181 81
Sotskov Y, Shakhlevich NV. 1995. NP-hardness of shop-scheduling problems with three jobs. Discrete Applied Mathematics. 237-266 59.3
SOTSKOV YN, SHAKHLEVICH NV. 1991. ADAPTIVE ALGORITHM FOR MINIMIZING TOTAL REQUEST SERVICING TIME BY SERIAL DEVICES. SOVIET JOURNAL OF COMPUTER AND SYSTEMS SCIENCES. 43-47 29.6
SOTSKOV YN, SHAKHLEVICH NV. 1995. NP-HARDNESS OF SHOP-SCHEDULING PROBLEMS WITH 3 JOBS. DISCRETE APPLIED MATHEMATICS. 237-266 59.3
Strusevich V, Drobouchevitch IG, Shakhlevich NV. 2002. Three-machine shop scheduling with partially ordered processing routes. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY. 574-582 53.5
Strusevich VA, Drobouchevitch IG, Shakhlevitch N. 2002. Three-machine shop scheduling with partially ordered processing routes. Journal of the Operational Research Society. 574-582 53.5
STRUSEVICH VA, SHAKHLEVICH NV. 1993. OPTIMAL JOB-SHOP SCHEDULING WITH 2 JOBS IN SYSTEMS WITH UNRESTRICTED PATHS. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS. 593-601 33.5
Thomassé S, Trotignon N, Vusković K. 2013. Parameterized algorithm for weighted independent set problem in bull-free graphs. Parameterized algorithm for weighted independent set problem in bull-free graphs. Algorithmica, November 2015, 1--23.
Trotignon N, Vuskovic K. 2010. A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences. Journal of Graph Theory. 31-67 63.1
Trotignon N, Vuskovic K. 2011. On Roussel-Rubio-type lemmas and their consequences. Discrete Mathematics. 684-687 311.8-9
Trotignon N, Vuskovic K. 2012. Combinatorial optimization with 2-joins. Journal of Combinatorial Theory: Series B. 153-185 102.1
Trotignon N, Vuskovic K. 2013. Combinatorial optimization with 2-joins.. CoRR. abs/1309.1547
Vuskovic K. 2010. Even-Hole-Free Graphs: A Survey. Applicable Analysis and Discrete Mathematics. 219-240 4.2
Weiß C, Knust S, Shakhlevitch NV, Waldherr S. 2016. The Assignment Problem with Nearly Monge Arrays and Incompatible Partner Indices. Discrete Applied Mathematics. 183-203 211
Wren A, Fores S, Kwan A, Kwan R, Parker M, Proll L. 2003. A flexible system for scheduling drivers. Journal of Scheduling. 437-455 6.5
Wren A, Kwan RS. 1999. Installing an urban transport scheduling system. Journal of Scheduling. 3-17 2
Chakhlevitch N (2014) On general methodology for solving inverse scheduling problems New Challenges in Scheduling Theory. Aussois, France

No publications to show.