×

zbMATH — the first resource for mathematics

Graph-theoretic concepts in computer science. 31st international workshop, WG 2005, Metz, France, June 23–25, 2005. Revised selected papers. (English) Zbl 1098.68004
Lecture Notes in Computer Science 3787. Berlin: Springer (ISBN 3-540-31000-2/pbk). xiv, 470 p. (2005).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding workshop has been reviewed (see Zbl 1067.68006).
Indexed articles:
Gottlob, Georg; Grohe, Martin; Musliu, Nysret; Samer, Marko; Scarcello, Francesco, Hypertree decompositions: structure, algorithms, and applications, 1-15 [Zbl 1126.68516]
Bouvel, Mathilde; Grebinski, Vladimir; Kucherov, Gregory, Combinatorial search on graphs motivated by bioinformatics applications: a brief survey, 16-27 [Zbl 1126.68514]
Aggarwal, Divesh; Mehta, Shashank K.; Deogun, Jitender S., Domination search on graphs with low dominating-target-number, 28-37 [Zbl 1126.68513]
Crespelle, Christophe; Paul, Christophe, Fully dynamic algorithm for recognition and modular decomposition of permutation graphs, 38-48 [Zbl 1126.68515]
Oum, Sang-il, Approximating rank-width and clique-width quickly, 49-58 [Zbl 1126.05304]
Giménez, Omer; Hliněný, Petr; Noy, Marc, Computing the Tutte polynomial on graphs of bounded clique-width, 59-68 [Zbl 1126.05302]
Gurski, Frank; Wanke, Egon, Minimizing NLC-width is NP-complete. (Extended abstract), 69-80 [Zbl 1171.05427]
Havet, Frédéric; Sereni, Jean-Sébastien, Channel assignment and improper choosability of graphs, 81-90 [Zbl 1171.05333]
Meister, Daniel, Computing treewidth and minimum fill-in for permutation graphs in linear time, 91-102 [Zbl 1171.05431]
Liedloff, Mathieu; Kloks, Ton; Liu, Jiping; Peng, Sheng-Lung, Roman domination over some graph classes, 103-114 [Zbl 1171.05389]
Fiala, Jiří; Paulusma, Daniël; Telle, Jan Arne, Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms, 115-126 [Zbl 1171.05425]
Beerliova, Zuzana; Eberhard, Felix; Erlebach, Thomas; Hall, Alexander; Hoffmann, Michael; Mihaák, Matúš; Ram, L. Shankar, Network discovery and verification, 127-138 [Zbl 1171.68587]
Gioan, Emeric, Complete graph drawings up to triangle mutations, 139-150 [Zbl 1171.05323]
Corneil, Derek G.; Dragan, Feodor F.; Köhler, Ekkehard; Yan, Chenyu, Collective tree 1-spanners for interval graphs, 151-162 [Zbl 1171.05370]
Le, Van Bang; Mosca, Raffaele; Müller, Haiko, On stable cutsets in claw-free graphs and planar graphs, 163-174 [Zbl 1171.68628]
Bose, Prosenjit; Dujmović, Vida; Wood, David R., Induced subgraphs of bounded degree and bounded treewidth, 175-186 [Zbl 1171.05400]
Heggernes, Pinar; Lokshtanov, Daniel, Optimal broadcast domination of arbitrary graphs in polynomial time, 187-198 [Zbl 1171.05386]
Berry, Anne; Krueger, Richard; Simonet, Genevieve, Ultimate generalizations of LexBFS and LEX M, 199-213 [Zbl 1171.68589]
Nikolopoulos, Stavros D.; Palios, Leonidas, Adding an edge in a cograph, 214-226 [Zbl 1171.68635]
Gatto, Michael; Jacob, Riko; Peeters, Leon; Schöbel, Anita, The computational complexity of delay management. (Extended abstract), 227-238 [Zbl 1171.90334]
Gonçalves, Daniel; Montassier, Mickaël, Acyclic choosability of graphs with small maximum degree, 239-248 [Zbl 1171.05332]
Nakano, Shin-ichi; Uno, Takeaki, Generating colored trees. (Extended abstract), 249-260 [Zbl 1171.68633]
Korach, Ephraim; Razgon, Margarita, Optimal hypergraph tree-realization, 261-270 [Zbl 1171.05375]
Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, 271-282 [Zbl 1171.92316]
Damaschke, Peter, On the fixed-parameter enumerability of cluster editing, 283-294 [Zbl 1171.05393]
Bodirsky, Manuel; Král’, Daniel, Locally consistent constraint satisfaction problems with binary constraints, 295-306 [Zbl 1171.68723]
Elsässer, Robert; Sauerwald, Thomas, On randomized broadcasting in star graphs, 307-318 [Zbl 1171.90355]
Tholey, Torsten, Finding disjoint paths on directed acyclic graphs, 319-330 [Zbl 1171.05348]
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent, Approximation algorithms for the bi-criteria weighted Max-Cut problem, 331-340 [Zbl 1171.90553]
Kako, Akihisa; Ono, Takao; Hirata, Tomio; Halldórsson, Magnús M., Approximation algorithms for the weighted independent set problem, 341-350 [Zbl 1171.68870]
van Leeuwen, Erik Jan, Approximation algorithms for unit disk graphs, 351-361 [Zbl 1171.68872]
Berthomé, Pascal; Lebresne, Sylvain; Nguyên, Kim, Computation of chromatic polynomials using triangulations and clique trees, 362-373 [Zbl 1171.05331]
Fomin, Fedor; Mazoit, Frédéric; Todinca, Ioan, Computing branchwidth via efficient triangulations and blocks, 374-384 [Zbl 1171.05426]
Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter, Algorithms based on the treewidth of sparse graphs, 385-396 [Zbl 1171.05428]
Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Extending the tractability border for closest leaf powers, 397-408 [Zbl 1171.68496]
Giesen, Joachim; Mitsche, Dieter, Bounding the misclassification error in spectral partitioning in the planted partition model, 409-420 [Zbl 1171.68616]
McConnell, Ross M.; de Montgolfier, Fabien, Algebraic operations on PQ trees and modular decomposition trees, 421-432 [Zbl 1171.68630]
Okamoto, Yoshio; Uno, Takeaki; Uehara, Ryuhei, Linear-time counting algorithms for independent sets in chordal graphs, 433-444 [Zbl 1171.68638]
Berry, Anne; Sigayret, Alain; Spinrad, Jeremy, Faster dynamic algorithms for chordal graphs, and an application to phylogeny, 445-455 [Zbl 1171.68590]
Nikolopoulos, Stavros D.; Palios, Leonidas, Recognizing HHDS-free graphs, 456-467 [Zbl 1123.68096]

MSC:
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68R10 Graph theory (including graph drawing) in computer science
00B25 Proceedings of conferences of miscellaneous specific interest
PDF BibTeX XML Cite
Full Text: DOI