![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
19. WG 1993: Utrecht, The Netherlands
- Jan van Leeuwen:
Graph-Theoretic Concepts in Computer Science, 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993, Proceedings. Lecture Notes in Computer Science 790, Springer 1994, ISBN 3-540-57899-4
Hard Problems on Classes of Graphs
- Sotiris E. Nikoletseas, Paul G. Spirakis:
Near-Optimal Dominating Sets in Dense Random Graphs in Polynomial Expected Time. 1-10 - N. W. Holloway, Somasundaram Ravindran, Alan Gibbons:
Approximating Minimum Weight Perfect Matchings for Complete Graphs Satisfying the Triangle Inequality. 11-20 - Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi:
Hierarchical Specified Unit Disk Graphs (Extended Abstract). 21-32
Structural Graph Theory
- Egon Wanke:
Bounded Tree-Width and LOGCFL. 33-44 - Hans L. Bodlaender
:
On Reduction Algorithms for Graphs with Small Treewidth. 45-56 - Martin Charles Golumbic, Haim Kaplan, Ron Shamir:
Algorithms and Complexity of Sandwich Problems in Graphs (Extended Abstract). 57-69
Dynamic Graph Algorithms
- Alberto Marchetti-Spaccamela
, Umberto Nanni
, Hans Rohnert:
On-line Graph Algorithms for Incremental Compilation. 70-86 - Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Xavier Messeguer:
Average Case Analysis of Fully Dynamic Connectivity for Directed Graphs. 87-98 - Zoran Ivkovic, Errol L. Lloyd:
Fully Dynamic Maintenance of Vertex Cover. 99-111 - Hans L. Bodlaender
:
Dynamic Algorithms for Graphs with Treewidth 2. 112-124
Structure-Oriented Graph Algorithms
- Andreas Brandstädt, Heinz-Jürgen Voss:
Short Disjoint Cycles in Graphs with Degree Constraints. 125-131 - Koichi Wada, Kimio Kawaguchi:
Efficient Algorithms for Tripartitioning Triconnected Graphs and 3-Edge-Connected Graphs. 132-143 - Zbigniew Lonc:
Toward a Solution of the Holyer's Problem. 144-152 - George Havas, Bohdan S. Majewski, Nicholas C. Wormald, Zbigniew J. Czech:
Graphs, Hypergraphs and Hashing. 153-165
Graph Coloring
- Ludek Kucera:
Coloring k-Colorable Graphs in Constant Expected Parallel Time. 166-176 - Ingo Schiermeyer:
Deciding 3-Colourability in Less Than O(1.415^n) Steps. 177-188 - Klaus Jansen:
A Rainbow About T-Colorings for Complete Graphs. 189-199 - Nai-Wei Lin:
Approximating the Chromatic Polynomial of a Graph. 200-210
AT-Free and Chordal Graphs
- Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Asteroidal Triple-Free Graphs. 211-224 - Elias Dahlhaus:
The Parallel Complexity of Elimination Ordering Procedures. 225-236 - Andreas Brandstädt, Feodor F. Dragan, Victor Chepoi, Vitaly I. Voloshin:
Dually Chordal Graphs. 237-251
Circuits and Nets
- Ingo Wegener:
The Size of Reduced OBDDs and Optimal Read-once Branching Programs for Almost all Boolean Functions. 252-263 - Jörg Desel:
Regular Marked Petri Nets. 264-275 - Javier Esparza
, Bernhard von Stengel:
The Asynchronous Committee Meeting Problem. 276-287
Graphs and Interconnection Networks
- Juraj Hromkovic, Ralf Klasing, Elena Stöhr:
Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks. 288-300 - Sabine R. Öhring, Sajal K. Das:
The Folded Petersen Network: A New Versatile Multiprocessor Interconnection Topology. 301-314 - Jacques E. Boillat:
Fast Load Balancing in Cayley Graphs and in Circuits. 315-326
Routing and Shortest Paths
- Farhad Shahrokhi, László A. Székely:
Concurrent Flows and Packet Routing in Cayley Graphs (Preliminary Version). 327-337 - Evangelos Kranakis, Danny Krizanc, S. S. Ravi:
On Multi-Label Linear Interval Routing Schemes (Extended Abstract). 338-349 - S. Haldar:
An 'All Pairs Shortest Path' Distributed Algorithm Using 2n² Messages. 350-363
Graph Embedding and Layout
- Koji Nakano
:
Linear Layouts of Generalized Hypercubes. 364-375 - Jianer Chen, Saroja P. Kanchi:
Graph Ear Decompositions and Graph Embeddings (Extended Abstract). 376-387 - Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, Imrich Vrto:
Improving Bounds for the Crossing Numbers on Surfaces of Genus g. 388-395 - Goos Kant, Xin He:
Two Algorithms for Finding Rectangular Duals of Planar Graphs. 396-410 - Goos Kant:
A More Compact Visibility Representation. 411-424
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.