Burkhard Monien

Orcid: 0000-0003-2334-6795

Affiliations:
  • University of Paderborn, Germany


According to our database1, Burkhard Monien authored at least 190 papers between 1970 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Which is the Worst-Case Nash Equilibrium?
SIAM J. Discret. Math., 2024

2022
(In)Existence of Equilibria for 2-Player, 2-Value Games with Semistrictly Quasiconcave Cost Functions.
Theory Comput. Syst., 2022

2021
The complexity of (E+Var)-equilibria, ESR-equilibria, and SuperE-equilibria for 2-players games with few cost values.
Theor. Comput. Sci., 2021

2020
Conditional Value-at-Risk: Structure and complexity of equilibria.
Theor. Comput. Sci., 2020

(In)Existence of Equilibria for 2-Players, 2-Values Games with Concave Valuations.
CoRR, 2020

2018
Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube.
J. Graph Theory, 2018

<i>NP</i> NP -Hardness of Equilibria in Case of Risk-Averse Players.
Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2016
The complexity of equilibria for risk-modeling valuations.
Theor. Comput. Sci., 2016

2015
Minimizing Expectation Plus Variance.
Theory Comput. Syst., 2015

The complexity of pure equilibria in mix-weighted congestion games on parallel links.
Inf. Process. Lett., 2015

Weighted Boolean Formula Games.
Proceedings of the Algorithms, Probability, Networks, and Games, 2015

2014
Preface to the self-portrayals of the GI Junior Fellows.
it Inf. Technol., 2014

2013
On the <i>PLS</i>-complexity of maximum constraint assignment.
Theor. Comput. Sci., 2013

How many attackers can selfish defenders catch?
Discret. Appl. Math., 2013

2012
Computing Nash Equilibria for Two-Player Restricted Network Congestion Games is -Complete.
Parallel Process. Lett., 2012

Report form the EATCS General Assembly.
Bull. EATCS, 2012

Letter from the President.
Bull. EATCS, 2012

Selfish Distributed Optimization.
Proceedings of the Euro-Par 2012 Parallel Processing - 18th International Conference, 2012

2011
Routing (un-) splittable flow in games with player-specific affine latency functions.
ACM Trans. Algorithms, 2011

Exact Price of Anarchy for Polynomial Congestion Games.
SIAM J. Comput., 2011

2010
Preface.
Theory Comput. Syst., 2010

Computing Nash Equilibria for Scheduling on Restricted Parallel Links.
Theory Comput. Syst., 2010

Local Search: Simple, Successful, But Sometimes Sluggish.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

On the Power of Nodes of Degree Four in the Local Max-Cut Problem.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009
Graph partitioning and disturbed diffusion.
Parallel Comput., 2009

A new diffusion-based multilevel algorithm for computing graph partitions.
J. Parallel Distributed Comput., 2009

Fair cost-sharing methods for scheduling jobs on parallel machines.
J. Discrete Algorithms, 2009

Nash Equilibria for Voronoi Games on Transitive Graphs.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

MultiProcessor Scheduling is PLS-Complete.
Proceedings of the 42st Hawaii International International Conference on Systems Science (HICSS-42 2009), 2009

From State-of-the-Art Static Fleet Assignment to Flexible Stochastic Planning of the Future.
Proceedings of the Algorithmics of Large and Complex Networks - Design, 2009

2008
Der Alphabeta-Algorithmus für Spielbäume: Wie bringe ich meinen Computer zum Schachspielen?.
Proceedings of the Taschenbuch der Algorithmen, 2008

A new model for selfish routing.
Theor. Comput. Sci., 2008

Selfish Routing with Incomplete Information.
Theory Comput. Syst., 2008

Nash equilibria in discrete routing games with convex latency functions.
J. Comput. Syst. Sci., 2008

On the Road to -Completeness: 8 Agents in a Singleton Congestion Game.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Voronoi Games on Cycle Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

A new diffusion-based multilevel algorithm for computing graph partitions of very high quality.
Proceedings of the 22nd IEEE International Symposium on Parallel and Distributed Processing, 2008

2007
Approximation Algorithms for Multilevel Graph Partitioning.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

A faster combinatorial approximation algorithm for scheduling unrelated parallel machines.
Theor. Comput. Sci., 2007

To Be or Not to Be (Served).
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Routing and Scheduling with Incomplete Information.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Congestion Games with Player-Specific Constants.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

The Power of Two Prices: Beyond Cross-Monotonicity.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006
The price of anarchy for polynomial social cost.
Theor. Comput. Sci., 2006

A 5/4-approximation algorithm for scheduling identical malleable tasks.
Theor. Comput. Sci., 2006

The Price of Anarchy for Restricted Parallel Links.
Parallel Process. Lett., 2006

Introduction.
J. Parallel Distributed Comput., 2006

Distributing Unit Size Workload Packages in Heterogeneous Networks.
J. Graph Algorithms Appl., 2006

Upper bounds on the bisection width of 3- and 4-regular graphs.
J. Discrete Algorithms, 2006

Wardrop Equilibria and Price of Stability for Bottleneck Games with Splittable Traffic.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Scheduling Unrelated Parallel Machines Computational Results.
Proceedings of the Experimental Algorithms, 5th International Workshop, 2006

Selfish Routing in Networks.
Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006

Accelerating shape optimizing load balancing for parallel FEM simulations by algebraic multigrid.
Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), 2006

Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

New trends in parallel and distributed computing - 6th international Heinz Nixdorf symposium, January 17 - 18, 2006, Heinz Nixdorf MuseumsForum: within the scope of the DFG Collaborative Research Centre 376 Massively Parallel Computing: algorithms, design, methods, applications.
HNI-Verlagsschriftenreihe 181, Heinz Nixdorf Institut, ISBN: 978-3-939350-00-2, 2006

2005
Structure and complexity of extreme Nash equilibria.
Theor. Comput. Sci., 2005

Edge-disjoint spanning trees for the generalized butterfly networks and their applications.
J. Parallel Distributed Comput., 2005

A Simple Graph-Theoretic Model for Selfish Restricted Scheduling.
Proceedings of the Internet and Network Economics, First International Workshop, 2005

Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
Error analysis in minimax trees.
Theor. Comput. Sci., 2004

New spectral lower bounds on the bisection width of graphs.
Theor. Comput. Sci., 2004

Improved bounds on cutwidths of shuffle-exchange and de Bruijn graphs.
Parallel Process. Lett., 2004

Optimal Diffusion Schemes And Load Balancing On Product Graphs.
Parallel Process. Lett., 2004

Graph Partitioning with the Party Library: Helpful-Sets in Practice.
Proceedings of the 16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2004), 2004

Load Balancing in Dynamic Networks.
Proceedings of the 7th International Symposium on Parallel Architectures, 2004

Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks.
Proceedings of the Algorithms, 2004

2003
Sparse topologies with small spectrum size.
Theor. Comput. Sci., 2003

On Spectral Bounds for the k-Partitioning of Graphs.
Theory Comput. Syst., 2003

Selfish Routing in Non-Cooperative Networks: A Survey.
Bull. EATCS, 2003

Load balancing of unit size tokens and expansion properties of graphs.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Which Is the Worst-Case Nash Equilibrium?
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Extreme Nash Equilibria.
Proceedings of the Theoretical Computer Science, 8th Italian Conference, 2003

Nashification and the Coordination Ratio for a Selfish Routing Game.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Fault Tolerances Analysis of Distributed Reconfigurable Systems Using SAT-Based Techniques.
Proceedings of the Field Programmable Logic and Application, 13th International Conference, 2003

SAT-Based Techniques in System Synthesis.
Proceedings of the 2003 Design, 2003

The Aircraft Sequencing Problem.
Proceedings of the Computer Science in Perspective, Essays Dedicated to Thomas Ottmann, 2003

2002
Diffusion Schemes for Load Balancing on Heterogeneous Networks.
Theory Comput. Syst., 2002

The Secret of Selective Game Tree Search, When Using Random-Error Evaluations.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

On the Problem of Scheduling Flows on Distributed Networks.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Toward Optimal Diffusion Matrices.
Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002

2001
Scalable Sparse Topologies with Small Spectrum.
Proceedings of the STACS 2001, 2001

New spectral bounds on k-partitioning of graphs.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

2000
Quality matching and local improvement for multilevel graph-partitioning.
Parallel Comput., 2000

Diffusive load balancing schemes on heterogeneous networks.
Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

Towards Optimal Load Balancing Topologies.
Proceedings of the Euro-Par 2000, Parallel Processing, 6th International Euro-Par Conference, Munich, Germany, August 29, 2000

A Distributed Algorithm to Evaluate Quantified Boolean Formulae.
Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30, 2000

1999
Efficient schemes for nearest neighbor load balancing.
Parallel Comput., 1999

The Latest Information on the 9<sup>th</sup> World Computer-Chess Championship.
J. Int. Comput. Games Assoc., 1999

More Information on the 9<sup>th</sup> World Computer-Chess Championship.
J. Int. Comput. Games Assoc., 1999

Programme of the ACC9 Conference.
J. Int. Comput. Games Assoc., 1999

Call for Participation: Advances in Computer Chess 9 Conference.
J. Int. Comput. Games Assoc., 1999

Optimal and Alternating-Direction Load Balancing Schemes.
Proceedings of the Euro-Par '99 Parallel Processing, 5th International Euro-Par Conference, Toulouse, France, August 31, 1999

1998
Specifying Resources and Services in Metacomputing Environments.
Parallel Comput., 1998

Compressing cube-connected cycles and butterfly networks.
Networks, 1998

Optimal Embedding of Complete Binary Trees into Lines and Grids.
J. Parallel Distributed Comput., 1998

The 9<sup>th</sup> World Computer-Chess Championship.
J. Int. Comput. Games Assoc., 1998

Call for Papers Advances in Computer Chess 9 Conference.
J. Int. Comput. Games Assoc., 1998

Embedding ladders and caterpillars into the hypercube.
Discret. Appl. Math., 1998

Parallel Decomposition of Unstructured FEM-Meshes.
Concurr. Pract. Exp., 1998

Nearest Neighbor Load Balancing on Graphs.
Proceedings of the Algorithms, 1998

An Integrated Approach to Semantic Evaluation and Content-Based Retrieval of Multimedia Documents.
Proceedings of the Research and Advanced Technology for Digital Libraries, 1998

1997
The Construction of Large Scale Reconfigurable Parallel Computing Systems (The Architecture of the SC320).
Int. J. Found. Comput. Sci., 1997

A Better Upper Bound on the Bisection Width of de Bruijn Networks (Extended Abstract).
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

A Local Graph Partitioning Heuristic Meeting Bisection Bounds.
Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, 1997

Parallel Sparse Cholesky Factorization.
Proceedings of the Solving Irregularly Structured Problems in Parallel, 1997

Online Scheduling of Continuous Media Streams.
Proceedings of the Foundations of Computer Science: Potential - Theory, 1997

1996
Combining Helpful Sets and Parallel Simulated Annealing for the Graph-partitioning Problem.
Parallel Algorithms Appl., 1996

On the Communication Throughput of Buffered Multistage Interconnection Networks.
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

Mapping tree-structured combinatorial optimization problems onto parallel computers.
Proceedings of the Solving Combinatorial Optimization Problems in Parallel, 1996

1995
Verteilte Spielbaumsuche.
Informationstechnik Tech. Inform., 1995

Nearest-neighbor algorithms for load-balancing in parallel computers.
Concurr. Pract. Exp., 1995

Performance evaluation of load distribution strategies in parallel branch and bound computations.
Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing, 1995

Towards developing universal dynamic mapping algorithms.
Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing, 1995

An analytical comparison of nearest neighbor algorithms for load balancing in parallel computers.
Proceedings of IPPS '95, 1995

Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network.
Proceedings of IPPS '95, 1995

A parallel local-search algorithm for the k-partitioning problem.
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS-28), 1995

A Parallel Simulated Annealing Algorithm for Generating 3D Layouts of Undirected Graphs.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1995

Efficient Use of Parallel & Distributed Systems: From Theory to Practice.
Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

1994
Corrigendum: Fast Recognition of Deterministic CFL's with a Smaller Number of Processors.
Theor. Comput. Sci., 1994

Note on Optimal Gossiping in Some Weak-Connected Graphs.
Theor. Comput. Sci., 1994

Broadcasting in Butterfly and deBruijn Networks.
Discret. Appl. Math., 1994

Optimal algorithms for dissemination of information in generalized communication modes.
Discret. Appl. Math., 1994

Sorting large data sets on a massively parallel system.
Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing, 1994

Studying Overheads in Massively Parallel MIN/MAX-Tree Evaluation.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Communication Throughput of Interconnection Networks.
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

Using helpful sets to improve graph bisections.
Proceedings of the Workshop on Interconnection Networks and Mapping and Scheduling Parallel Computations, 1994

1993
Fast recognition of deterministic cfl's with a smaller number of processors.
Theor. Comput. Sci., 1993

Optimal Algorithms for Dissemination of Information in Some Interconnection Networks.
Algorithmica, 1993

Parallel Architectures: Design and Efficient Use.
Proceedings of the STACS 93, 1993

A Dynamic Distributed Load Balancing Algorithm with Provable Good Performance.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

1992
Mapping und Lastverteilung in parallelen Systemen.
Proceedings of the Parallele Datenverarbeitung mit dem Transputer, 1992

Optimal Algorithms for Disemination of Information in Generalized Communication Modes.
Proceedings of the PARLE '92: Parallel Architectures and Languages Europe, 1992

A Realizable Efficient Parallel Architecture.
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

Load Balancing for Distributed Branch and Bound Algorithms.
Proceedings of the 6th International Parallel Processing Symposium, 1992

Distributed Game Tree Search on a Massively Parallel System.
Proceedings of the Data Structures and Efficient Algorithms, 1992

The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems).
Proceedings of the Informatik, Festschrift zum 60. Geburtstag von Günter Hotz, 1992

1991
On the Parallel Recognition of Unambiguous Context-Free Languages.
Theor. Comput. Sci., 1991

Bandwidth Minimization: An Approximation Algorithm for Caterpillars.
Math. Syst. Theory, 1991

Implementierung von Simulated Annealing auf Transputer-Systemen.
Proceedings of the Parallele Datenverarbeitung mit dem Transputer, 1991

Load balancing in large networks: a comparative study.
Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, 1991

Simulating Binary Trees on X-Trees (Extended Abstract).
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems).
Proceedings of the Mathematical Foundations of Computer Science 1991, 1991

1990
Response to a Comment on 'Distributed Game-Tree Search'.
J. Int. Comput. Games Assoc., 1990

An Improved Algorithm to Detect Communication Deadlocks in Distributed Systems.
Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Caterpillars and Context-Free Languages.
Proceedings of the STACS 90, 1990

Approximation algorithms for the bandwidth minimization problem for caterpillar graphs.
Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, 1990

Optimal Algorithms for Dissemination of Information in Some Interconnection Networks (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989
Distributed Game-Tree Search.
J. Int. Comput. Games Assoc., 1989

WEighted Parallel Triangulation of Simple Polygons.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1989

Two Strategies for Solving the Vertex Cover Problem on a Transputer Network.
Proceedings of the Distributed Algorithms, 1989

On the Number of Rounds Necessary to Disseminate Information.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988
Min Cut is NP-Complete for Edge Weighted Treees.
Theor. Comput. Sci., 1988

Bandwidth and Profile Minimization.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1988

Comparing Interconnection Networks.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

Simulating Binary Trees on Hypercubes.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Parallel Processing of Combinatorial Search.
Proceedings of the Parallel Algorithms and Architectures, 1987

Superlinear Speedup for Parallel Backtracking.
Proceedings of the Supercomputing, 1987

1986
Min Cut is NP-Complete for Edge Weigthed Trees.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
Bandwidth Constrained NP-Complete Problems.
Theor. Comput. Sci., 1985

Solving satisfiability in less than 2<sup>n</sup> steps.
Discret. Appl. Math., 1985

Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem.
Acta Informatica, 1985

On the Complexity of Deadlock Recovery.
Proceedings of the STACS 85, 1985

The complexity of embedding graphs into binary trees.
Proceedings of the Fundamentals of Computation Theory, 1985

1984
Deterministic Two-Way One-Head Pushdown Automata are Very Powerful.
Inf. Process. Lett., 1984

1983
The complexity of determining a shortest cycle of even length.
Computing, 1983

The Complexity of Determining Paths of Length k.
Proceedings of the WG '83, 1983

Some Further Approximation Algorithms for the Vertex Cover Problem.
Proceedings of the CAAP'83, 1983

1982
On Eliminating Nondeterminism from Turing Machines which Use less than Logarithm Worktape Space.
Theor. Comput. Sci., 1982

The Complexity of Determing a Shortest Cycle of Even Length.
Proceedings of the 8th Conference Graphtheoretic Concepts in Computer Science (WG '82), 1982

1981
Four Approximation Algorithms for the Feedback Vertex Set Problem.
Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), 1981

Time and Space Bounded Complexity Classes and Bandwidth Constrained Problems (A Survey).
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report).
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

On the LBA Problem.
Proceedings of the Fundamentals of Computation Theory, 1981

1980
Two-Way Multihead Automata Over a One-Letter Alphabet.
RAIRO Theor. Informatics Appl., 1980

Bounding the Bandwidth of NP-Complete Problems.
Proceedings of the Graphtheoretic Concepts in Computer Science, 1980

On a Subclass of Pseudopolynomial Problems.
Proceedings of the Mathematical Foundations of Computer Science 1980 (MFCS'80), 1980

1979
On Eliminating Nondeterminism From Turing Machines Which Use Less Than Logarithmic Worktape Space.
Proceedings of the Automata, 1979

1977
Corrigenda: Transformational Methods and Their Application to Complexity Problems
Acta Informatica, 1977

The LBA-Problem and the Deterministic Tape Complexity of Two-Way One-Counter Languages over a One-Letter Alphabet.
Acta Informatica, 1977

The LBA-problem and the transormability of the class epsilon<sup>2</sup>.
Proceedings of the Theoretical Computer Science, 1977

About the Derivation Languages of Grammars and Machines.
Proceedings of the Automata, 1977

1976
A Recursive and a Grammatical Characterization of the Exponential-Time Languages.
Theor. Comput. Sci., 1976

Transformational Methods and their Application to Complexity Problems.
Acta Informatica, 1976

1975
Relationships between Pushdown Automata with Counters and Complexity Classes.
Math. Syst. Theory, 1975

About the deterministic simulation of nondeterministic (log n)-tape bounded Turing machines.
Proceedings of the Automata Theory and Formal Languages, 1975

1974
Beschreibung von Zeitkomplexitätsklassen bei Turingmaschinen durch andere Automatenmodelle.
J. Inf. Process. Cybern., 1974

Characterizations of Time-Bounded Computations by Limited Primitive Recursion.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974

1973
On the simulation of time bounded machines.
Proceedings of the 1. Fachtagung über Automatentheorie und Formale Sprachen, 1973

1972
Relationship between Pushdown Automata and Tape-Bounded Turing Machines.
Proceedings of the Automata, 1972

1970
Über die Konvergenzordnung von Differenzenverfahren, die parabolische Anfangsrandwertaufgaben approximieren.
Computing, 1970


  Loading...