Publications
Algorithms and Complexity
2022
2022. Induced subgraphs and tree decompositions V. One neighbor in a hole.
2022. Induced subgraphs and tree decompositions V. Small components of big
vertices.
2022. When all holes have the same length.
2021
2021. Induced subgraphs and tree decompositions II. Toward walls and their
line graphs in graphs of bounded degree.
2021. Submodular functions and perfect graphs.
2021. Graphs with all holes the same length.
2020
2020. Induced subgraphs and tree decompositions I. Even-hole-free graphs of
bounded degree.
2019
2019. Maximum independent sets in (pyramid, even hole)-free graphs.. CoRR. abs/1912.11246
2018
2017
2016 & previous
2004. Linear programming. In: Goodman JE; O'Rourke J (eds.) Handbook of Discrete and Computational Geometry. 2.
2004. Bus and train driver scheduling. In: Leung JY-T (eds.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis.
1996. Scalable and portable computing using the WPRAM model.
1995. Designing practical parallel algorithms for scalable message passing machines.
1994. On the Greedy Heuristic for Matchings.. Proceedings of the 5th ACM/SIAM Symposium on Discrete Algorithms
2005. Path coupling using stopping times. Fundamentals of Computation Theory, 15th International Symposium, FCT2005
2006. Stopping times, metrics and approximate counting. Automata, Languages and Programming: 33rd International Colloquium, Proceedings
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
2003. LiSA - fit for cooperative development. Sixth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'03)
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)
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
1998. Faster Random Generation of Linear Extensions.. Ninth Annual ACM/SIAM Symposium on Discrete Algorithms
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
2009. The flip markov chain and a randomising P2P protocol. Principles of Distributed Computing (PODC)
2001. On the tree-degree of graphs. Graph-Theoretic Concepts in Computer Science - 27th International Workshop (WG 2001)
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)
2004. Two-machine open shop scheduling problem with controllable processing times. Ninth International Workshop on Project Management and Scheduling (PMS'04)
1994. Recognizing Balanced 0, +/- Matrices.. Proceedings of the fifth annual ACM-SIAM symposium on Discrete Algorithms
2005. Sampling regular graphs and a peer-to-peer network (Extended Abstract). PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS
2005. Sampling regular graphs and a peer-too-peer network. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms
2010. Networks of random cycles. Symposium on Discrete Algorithms (SODA)
2003. A polynomial algorithm for recognizing perfect graphs. 44th Symposium on Foundations of Computer Science (FOCS 2003)
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)
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)
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)
2001. Randomly colouring graphs with lower bounds on girth and maximum degree. 42nd Annual Symposium on Foundations of Computer Science (FOCS'01)
1990. Probabilistic Analysis of the Generalised Assignment Problem.. Integer Programming and Combinatorial Optimization
1992. Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm.. Integer Programming and Combinatorial Optimization
2004. Randomly coloring constant degree graphs. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
1994. Approximately Counting Hamilton Cycles in Dense Graphs.. Proceedings of the 5th ACM/SIAM Symposium on Discrete Algorithms
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
2002. Counting and sampling H-colourings. Randomization and Approximation Techniques in Computer Science, 6th International Workshop (RANDOM 2002)
2006. Dobrushin conditions and systematic scan. Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques
2006. On Counting Homomorphisms to Directed Acyclic Graphs.. ICALP (1)
2000. The complexity of counting graph homomorphisms. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms
2002. Rapidly mixing Markov Chains for dismantleable constraint graphs. Randomization and Approximation Techniques in Computer Science 6th International Workshop (RANDOM 2002)
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
1977. Vertex enumeration in convex polyhedra - a comparative computational study. Proceedings of the CP77 Combinatorial Programming Conference
2010. On the complexity of #CSP. 42nd ACM Symposium on Theory of Computing (STOC 2010)
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)
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
2009. Genetic and local search algorithms for train crew rostering. 11th International Conference on Advanced Systems for Public Transport (CASPT)
2003. Constraint-based local search for rail container service planning. MISTA 2003 Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications
2004. Demand responsive scheduling of rail container traffic. Proceedings of the 10th World Transport Research Conference
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
2003. On the recognition of general partition graphs. Graph-Theoretic Concepts in Computer Science - 29th International Workshop,WG 2001
2003. Feedback vertex set and longest induced path on AT-free graphs. Graph-Theoretic Concepts in Computer Science - 29th International Workshop,WG 2003
2009. Case studies of TrainTRACS under contrasting train crew scheduling scenarios. 11th International Conference on Advanced Systems for Public Transport (CASPT)
2003. Recent advancement in an established driver scheduling system. MISTA 2003 Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications
2004. Recent advances in TRACS. CASPT 2004 Proceedings
2009. Case studies of successful train crew scheduling. 4th Multidisciplinary International Conference on Scheduling : Theory and Applications
2003. A co-evolutionary algorithm for train timetabling. 2003 Congress on Evolutionary Computation
2003. A co-evolutionary approach for train timetabling. MISTA 2003 Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications
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
2005. On stable cutsets in claw-free graphs and planar graphs. Graph-Theoretic Concepts in Computer Science: 31st International Workshop, WG 2005
2001. Evolutionary driver scheduling with fuzzy evaluation. Proceedings of the Graduate Student Workshop at Genetic and Evolutionary Computation Conference
2001. A fuzzy simulated evolution algorithm for the driver scheduling problem. 2001 Congress on Evolutionary Computation (CEC2001)
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
2002. A fuzzy evolutionary approach with Taguchi parameter setting for the set covering problem. Proceedings of the Congress on Evolutionary Computation, Honolulu, May 2002
2009. Real world optimisation through spin out activity. 4th Multidisciplinary International Conference on Scheduling : Theory and Applications
2003. Generation and optimization of train timetables using coevolution. Genetic and Evolutionary Computation - GECCO 2003
2005. On some issues of inverse scheduling. Seventh Workshop on Models and Algorithms for Planning and Scheduling (MAPSP'05)
2003. On two bicriteria scheduling problems with controllable processing times. Sixth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'03)
2001. A constructive approach to bus and train driver scheduling. Proceedings of the 10th Annual Industrial Engineering Research Conference
2001. Tabu search for driver scheduling. Computer-Aided Scheduling of Public Transport
1994. AN ADAPTIVE APPROACH IN PRODUCTION SCHEDULING BASED ON THE MIXED GRAPH MODEL. SECOND INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS ENGINEERING
2013. Graphs that do not contain a cycle with a node that has at least two neighbors on it.. CoRR. abs/1309.1841
2005. Metric Construction, Stopping Times and Path Coupling.. Electron. Colloquium Comput. Complex..
2007. Path coupling without contraction. Journal of Discrete Algorithms. 280-292 5
2001. On treewidth approximations. Electronic Notes in Discrete Mathematics. 1-4 8
2012. The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences. 681-688 78.2
2011. Log-supermodular functions, functional clones and counting CSPs. CoRR. abs/1108.5288
2006. Scheduling with controllable release dates and processing times: Total completion time minimization. European Journal of Operational Research. 769-781+ 175
1999. Proportionate flow shop with controllable processing times. Journal of Scheduling. 253-265 2.6
2001. Balanced 0, +/- 1 matrices I. Decomposition. J COMB THEORY B. 243-274 81.2
2011. On the Imitation Strategy for Games on Graphs. CoRR. abs/1102.3879
2006. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures & Algorithms. 450-465 29
2003. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Structures & Algorithms. 167-179 23.2
1989. Randomized algorithm for fixed-dimensional linear programming. Mathematical Programming, Series A. 203-212 44.2
2010. The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract). CoRR. abs/1001.4987
2007. The Complexity of Weighted Boolean #CSP. CoRR. abs/0704.3683
2008. A complexity dichotomy for hypergraph partition functions. CoRR. abs/0811.0037
2006. Systematic scan for sampling colorings. Annals of Applied Probability. 185-230 16
2008. Dobrushin conditions and systematic scan. Combinatorics, Probability & Computing. 761-779 17.6
2010. A Complexity Dichotomy For Hypergraph Partition Functions. Computational Complexity. 605-633 19.4
2006. Markov chain comparison. Probability Surveys. 89-111 3
2011. The Iterated Prisoner's Dilemma on a Cycle. CoRR. abs/1102.3822
1977. An algorithm for determining all extreme points of a convex polytope. Mathematical Programming. 81-96 12
1980. Eliminating extraneous edges in Greenberg's algorithm. Mathematical Programming. 106-110 19
1982. An improved vertex enumeration algorithm. European Journal of Operational Research. 359-368 9
2010. The Complexity of #CSP. CoRR. abs/1003.3879
2000. Fast and optimal parallel multidimensional search in prams with applications to linear programming and related problems. SIAM J COMPUT. 1443-1461 30.5
2006. Computational complexity of stochastic programming problems. Mathematical Programming. 423-432 106
1998. Dominance in multi-dimensional multiple-choice knapsack problems. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH. 159-168 15.2
2013. Algorithms for square-$3PC(\cdot, \cdot)$-free Berge graphs.. CoRR. abs/1309.0694
1996. On edge perfectness and classes of bipartite graphs. Discrete Mathematics. 159-187 149
1997. Recognizing interval digraphs and interval bigraphs in polynomial time. Discrete Applied Mathematics. 189-205 78
1996. A scalable shared queue on a distributed memory machine. Computer Journal. 39.6
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
1991. ADAPTIVE ALGORITHM FOR MINIMIZING TOTAL REQUEST SERVICING TIME BY SERIAL DEVICES. SOVIET JOURNAL OF COMPUTER AND SYSTEMS SCIENCES. 43-47 29.6
1993. OPTIMAL JOB-SHOP SCHEDULING WITH 2 JOBS IN SYSTEMS WITH UNRESTRICTED PATHS. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS. 593-601 33.5
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.
2013. Combinatorial optimization with 2-joins.. CoRR. abs/1309.1547
1999. Installing an urban transport scheduling system. Journal of Scheduling. 3-17 2