dblp.uni-trier.dewww.uni-trier.de

Martin E. Dyer Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2009
105EEColin Cooper, Martin E. Dyer, Andrew J. Handley: The flip markov chain and a randomising P2P protocol. PODC 2009: 141-150
104EEMartin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby: The Complexity of Approximating Bounded-Degree Boolean #CSP CoRR abs/0907.2663: (2009)
103EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean CSP. SIAM J. Comput. 38(5): 1970-1986 (2009)
102EEAndrei Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby: The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci. 410(38-40): 3949-3961 (2009)
2008
101EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: A complexity dichotomy for hypergraph partition functions CoRR abs/0811.0037: (2008)
100EEAndrei Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby: The Complexity of Weighted Boolean #CSP with Mixed Signs CoRR abs/0812.4171: (2008)
99EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. Combinatorics, Probability & Computing 17(6): 761-779 (2008)
98EEMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms 32(3): 375-399 (2008)
97EEMary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie: Random walks on the vertices of transportation polytopes with constant number of sources. Random Struct. Algorithms 33(3): 333-355 (2008)
2007
96EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean #CSP CoRR abs/0704.3683: (2007)
95EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: An approximation trichotomy for Boolean #CSP CoRR abs/0710.4272: (2007)
94EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Matrix norms and rapid mixing for spin systems CoRR abs/math/0702744: (2007)
93EEColin Cooper, Martin E. Dyer, Catherine S. Greenhill: Sampling Regular Graphs and a Peer-to-Peer Network. Combinatorics, Probability & Computing 16(4): 557-593 (2007)
92EEMartin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs. J. ACM 54(6): (2007)
91EEMagnus Bordewich, Martin E. Dyer: Path coupling without contraction. J. Discrete Algorithms 5(2): 280-292 (2007)
2006
90EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. APPROX-RANDOM 2006: 327-338
89EEMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Stopping Times, Metrics and Approximate Counting. ICALP (1) 2006: 108-119
88EEMartin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) 2006: 38-49
87EEMartin E. Dyer, Leen Stougie: Computational complexity of stochastic programming problems. Math. Program. 106(3): 423-432 (2006)
86EEMartin E. Dyer, Abraham D. Flaxman, Alan M. Frieze, Eric Vigoda: Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms 29(4): 450-465 (2006)
85EEMary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin: Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. SIAM J. Comput. 36(1): 247-278 (2006)
2005
84EEMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times. FCT 2005: 19-31
83EEColin Cooper, Martin E. Dyer, Catherine S. Greenhill: Sampling regular graphs and a peer-to-peer network. SODA 2005: 980-988
82EEMary Cryan, Martin E. Dyer, Dana Randall: Approximately counting integral flows and cell-bounded contingency tables. STOC 2005: 413-422
81EEMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs Electronic Colloquium on Computational Complexity (ECCC)(002): (2005)
80EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin conditions and Systematic Scan Electronic Colloquium on Computational Complexity (ECCC)(075): (2005)
79EEMartin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs Electronic Colloquium on Computational Complexity (ECCC)(121): (2005)
78EEMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Metric Construction, Stopping Times and Path Coupling. Electronic Colloquium on Computational Complexity (ECCC)(151): (2005)
2004
77EEMartin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda: Randomly Coloring Constant Degree Graphs. FOCS 2004: 582-589
76EEMartin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda: Randomly coloring constant degree graphs Electronic Colloquium on Computational Complexity (ECCC)(009): (2004)
75EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and sampling H-colourings? Inf. Comput. 189(1): 1-16 (2004)
74EEMartin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz: Mixing in time and space for lattice spin systems: A combinatorial view. Random Struct. Algorithms 24(4): 461-479 (2004)
73EEMartin E. Dyer, Catherine S. Greenhill: Corrigendum: The complexity of counting graph homomorphisms. Random Struct. Algorithms 25(3): 346-352 (2004)
2003
72EESammani D. Abdullahi, Martin E. Dyer, Les G. Proll: Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems. DMTCS 2003: 89-96
71EEMary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie: Random walks on the vertices of transportation polytopes with constant number of sources. SODA 2003: 330-339
70EEMartin E. Dyer: Approximate counting by dynamic programming. STOC 2003: 693-699
69EEMartin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 (2003)
68EEMary Cryan, Martin E. Dyer: A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. J. Comput. Syst. Sci. 67(2): 291-310 (2003)
67EEMartin E. Dyer, Alan M. Frieze: Randomly coloring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms 23(2): 167-179 (2003)
66 Martin E. Dyer, Alan M. Frieze, Michael Molloy: A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theor. Comput. Sci. 290(3): 1815-1828 (2003)
2002
65EEMary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin: Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. FOCS 2002: 711-720
64EEMartin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz: Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. RANDOM 2002: 149-163
63EEMartin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and Sampling H-Colourings. RANDOM 2002: 51-67
62EEMartin E. Dyer, Mark Jerrum, Eric Vigoda: Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. RANDOM 2002: 68-77
61EEMary Cryan, Martin E. Dyer: A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. STOC 2002: 240-249
60 Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Gabriel Istrate, Mark Jerrum: Convergence Of The Iterated Prisoner's Dilemma Game Combinatorics, Probability & Computing 11(2): (2002)
59 Martin E. Dyer, Catherine S. Greenhill, Michael Molloy: Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs. Random Struct. Algorithms 20(1): 98-114 (2002)
58EEMartin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 31(5): 1527-1541 (2002)
2001
57 Martin E. Dyer, Alan M. Frieze: Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. FOCS 2001: 579-587
56 Colin Cooper, Martin E. Dyer, Alan M. Frieze: On Markov Chains for Randomly H-Coloring a Graph. J. Algorithms 39(1): 117-134 (2001)
2000
55EEMartin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: On the relative complexity of approximate counting problems. APPROX 2000: 108-119
54EEMartin E. Dyer, Catherine S. Greenhill: The complexity of counting graph homomorphisms (extended abstract). SODA 2000: 246-255
53EEMartin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher: An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). SODA 2000: 616-624
52 Martin E. Dyer, Catherine S. Greenhill: On Markov Chains for Independent Sets. J. Algorithms 35(1): 17-49 (2000)
51 Martin E. Dyer, Catherine S. Greenhill: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3-4): 260-289 (2000)
50EEMartin E. Dyer, Sandeep Sen: Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems. SIAM J. Comput. 30(5): 1443-1461 (2000)
49EEMartin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher: An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings. SIAM J. Comput. 30(6): 1962-1975 (2000)
48EEMartin E. Dyer, Catherine S. Greenhill: Polynomial-time counting and sampling of two-rowed contingency tables. Theor. Comput. Sci. 246(1-2): 265-278 (2000)
1999
47EEMartin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. FOCS 1999: 210-217
46EERuss Bubley, Martin E. Dyer: Faster random generation of linear extensions. Discrete Mathematics 201(1-3): 81-88 (1999)
45 Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum: On Approximately Counting Colorings of Small Degree Graphs. SIAM J. Comput. 29(2): 387-400 (1999)
1998
44EEMartin E. Dyer, Catherine S. Greenhill: A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables. ICALP 1998: 339-350
43 Russ Bubley, Martin E. Dyer: Faster Random Generation of Linear Extensions. SODA 1998: 350-354
42 Russ Bubley, Martin E. Dyer, Catherine S. Greenhill: Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing. SODA 1998: 355-363
41 Russ Bubley, Martin E. Dyer, Mark Jerrum: An elementary analysis of a procedure for sampling points in a convex body. Random Struct. Algorithms 12(3): 213-235 (1998)
40 Martin E. Dyer, Catherine S. Greenhill: A more rapidly mixing Markov chain for graph colorings. Random Struct. Algorithms 13(3-4): 285-317 (1998)
39 Martin E. Dyer, Peter Gritzmann, Alexander Hufnagel: On the Complexity of Computing Mixed Volumes. SIAM J. Comput. 27(2): 356-400 (1998)
38EEMartin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM J. Comput. 27(5): 1262-1272 (1998)
1997
37EERuss Bubley, Martin E. Dyer: Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. FOCS 1997: 223-231
36 Russ Bubley, Martin E. Dyer: Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT. SODA 1997: 248-257
35 Martin E. Dyer, Ravi Kannan, John Mount: Sampling contingency tables. Random Struct. Algorithms 10(4): 487-506 (1997)
1996
34EEJonathan M. Nash, Peter M. Dew, John R. Davy, Martin E. Dyer: Implementation Issues Relating to the WPRAM Model for Scalable Computing. Euro-Par, Vol. II 1996: 319-326
33EEBarbara M. Smith, Martin E. Dyer: Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artif. Intell. 81(1-2): 155-181 (1996)
32 Jonathan M. Nash, Peter M. Dew, Martin E. Dyer: A Scalable Shared Queue on a Distributed Memory Machine. Comput. J. 39(6): 483-495 (1996)
1995
31EEMartin E. Dyer, Jonathan M. Nash, Peter M. Dew: An Optimal Randomized Planar Convex Hull Algorithm With Good Empirical Performance. SPAA 1995: 21-26
30EEMartin E. Dyer: A Parallel Algorithm for Linear Programming in Fixed Dimension. Symposium on Computational Geometry 1995: 345-349
29EEAndrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, Eli Upfal: The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height. Inf. Process. Lett. 56(2): 79-81 (1995)
28 Martin E. Dyer, Trevor I. Fenner, Alan M. Frieze, Andrew Thomason: On Key Storage in Secure Networks. J. Cryptology 8(4): 189-200 (1995)
27 Martin E. Dyer, Alan M. Frieze, Stephen Suen: Ordering Clone Libraries in Computational Biology. Journal of Computational Biology 2(2): 207-218 (1995)
26 Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen: Randomized Greedy Matching II. Random Struct. Algorithms 6(1): 55-74 (1995)
1994
25 Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen: On the Greedy Heuristic for Matchings. SODA 1994: 141-149
24 Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Cycles in Dense Graphs. SODA 1994: 336-343
23EEMartin E. Dyer: On a Universal Chain Problem. Discrete Applied Mathematics 48(3): 219-229 (1994)
22 Martin E. Dyer, Alan M. Frieze: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64: 1-16 (1994)
1993
21 Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani: A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Combinatorics, Probability & Computing 2: 271-284 (1993)
1992
20 Martin E. Dyer, Alan M. Frieze: Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm. IPCO 1992: 72-84
19EEMartin E. Dyer: A Class of Convex Programs with Applications to Computational Geometry. Symposium on Computational Geometry 1992: 9-15
18 Martin E. Dyer, Alan M. Frieze: Probabilistic analysis of the generalised assignment problem. Math. Program. 55: 169-181 (1992)
17 Martin E. Dyer, Zoltán Füredi, Colin McDiarmid: Volumes Spanned by Random Points in the Hypercube. Random Struct. Algorithms 3(1): 91-106 (1992)
1991
16EEMartin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. J. ACM 38(1): 1-17 (1991)
15 Martin E. Dyer, Alan M. Frieze: Randomized Greedy Matching. Random Struct. Algorithms 2(1): 29-46 (1991)
14 Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph. Random Struct. Algorithms 2(2): 233-240 (1991)
13 Martin E. Dyer: On Counting Lattice Points in Polyhedra. SIAM J. Comput. 20(4): 695-707 (1991)
1990
12 Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of the Generalised Assignment Problem. IPCO 1990: 189-200
11EEMartin E. Dyer, Alan M. Frieze: On an optimization problem with nested constraints. Discrete Applied Mathematics 26(2-3): 159-173 (1990)
10EEMartin E. Dyer, Laurence A. Wolsey: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics 26(2-3): 255-270 (1990)
9 Martin E. Dyer, Alan M. Frieze: On Patching Algorithms for Random Asymmetric Travelling Salesman Problems. Math. Program. 46: 361-378 (1990)
1989
8 Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies STOC 1989: 375-381
7 Martin E. Dyer, Alan M. Frieze: The Solution of Some Random NP-Hard Problems in Polynomial Expected Time. J. Algorithms 10(4): 451-489 (1989)
1988
6 Martin E. Dyer, Alan M. Frieze: On the Complexity of Computing the Volume of a Polyhedron. SIAM J. Comput. 17(5): 967-974 (1988)
1986
5 Martin E. Dyer, Alan M. Frieze: Fast Solution of Some Random NP-Hard Problems FOCS 1986: 331-336
4 Martin E. Dyer, Alan M. Frieze: Planar 3DM is NP-Complete. J. Algorithms 7(2): 174-184 (1986)
3 Martin E. Dyer: On a Multidimensional Search Technique and its Application to the Euclidean One-Centre Problem. SIAM J. Comput. 15(3): 725-738 (1986)
1984
2 Martin E. Dyer, Alan M. Frieze: A Partitioning Algorithm for Minimum Weighted Euclidean Matching. Inf. Process. Lett. 18(2): 59-62 (1984)
1 Martin E. Dyer: Linear Time Algorithms for Two- and Three-Variable Linear Programs. SIAM J. Comput. 13(1): 31-45 (1984)

Coauthor Index

1Sammani D. Abdullahi [72]
2Jonathan Aronson [25] [26]
3Magnus Bordewich [78] [81] [84] [89] [91] [98]
4Andrei Z. Broder [29]
5Russ Bubley [36] [37] [41] [42] [43] [45] [46]
6Andrei Bulatov [100] [102]
7Colin Cooper [56] [83] [93] [105]
8Mary Cryan [61] [65] [68] [71] [82] [85] [97]
9John R. Davy [34]
10Peter M. Dew [31] [32] [34]
11Trevor I. Fenner [28]
12Abraham D. Flaxman (Abraham Flaxman) [86]
13Alan M. Frieze [2] [4] [5] [6] [7] [8] [9] [11] [12] [14] [15] [16] [18] [20] [21] [22] [24] [25] [26] [27] [28] [29] [38] [47] [56] [57] [58] [66] [67] [76] [77] [86]
14Zoltán Füredi [17]
15Leslie Ann Goldberg [49] [53] [55] [60] [63] [65] [69] [75] [79] [80] [85] [88] [90] [92] [94] [95] [96] [99] [100] [101] [102] [103] [104]
16Catherine S. Greenhill [40] [42] [44] [45] [48] [49] [51] [52] [53] [54] [55] [59] [60] [69] [73] [83] [93]
17Peter Gritzmann [39]
18Andrew J. Handley [105]
19Thomas P. Hayes [76] [77]
20Alexander Hufnagel [39]
21Gabriel Istrate [60]
22Markus Jalsenius [100] [102] [104]
23Mark Jerrum [24] [38] [41] [45] [47] [49] [53] [55] [58] [60] [62] [63] [65] [69] [75] [80] [85] [90] [94] [95] [96] [99] [101] [103]
24Ravi Kannan (Ravindran Kannan) [8] [16] [21] [35]
25Ajai Kapoor [21]
26Marek Karpinski [78] [81] [84] [89] [98]
27Russell A. Martin [65] [85]
28Colin McDiarmid (Colin J. H. McDiarmid) [17]
29Michael Mitzenmacher [49] [53]
30Michael Molloy (Michael S. O. Molloy) [59] [66]
31John Mount [35]
32Haiko Müller [71] [97]
33Jonathan M. Nash [31] [32] [34]
34Mike Paterson [79] [88] [92]
35Ljubomir Perkovic [21]
36Les G. Proll [72]
37Prabhakar Raghavan [29]
38Dana Randall [82]
39David Richerby [100] [102] [104]
40Sandeep Sen [50]
41Alistair Sinclair [64] [74]
42Barbara M. Smith [33]
43Leen Stougie [71] [87] [97]
44Stephen Suen [25] [26] [27]
45Andrew Thomason [28]
46Eli Upfal [29]
47Umesh V. Vazirani [21]
48Eric Vigoda [62] [64] [74] [76] [77] [86]
49Dror Weitz [64] [74]
50Laurence A. Wolsey [10]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)