Hromkovic

Graph-Theoretic Concepts in Computer Science

24th International Workshop, WG'98, Smolenice Castle, Slovak Republic, June 18-20, Proceedings
Herausgegeben:Hromkovic, Juraj; Sykora, Ondrej

• Broschiertes Buch

Produktbeschreibung

This book constitutes the thoroughly refereed post-workshop proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'98, held in Smolenice Castle, Slovak Republic, in June 1998.The 30 revised full papers presented were carefully selected from a total of 61 submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms and graph-theoretic applications in computer science.

---

The International Workshop on Graph-Theoretic Concepts in Computer Science is one of the most traditional and high quality conferences in Computer Science. PreviousconferenceswereorganizedatvariousplacesinAustria,Germany,Italy, and the Netherlands. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research. The workshop is well-balanced with respect to established researchers and young scientists. th The24 InternationalWorkshoponGraph-TheoreticConceptsinComputer Science(WG 98)washeldatSmoleniceCastle,nearBratislava,SlovakRepublic, June 18 20, 1998. It was organized by the Slovak Academy of Computer Science in cooperation with the Department of Computer Science I at RWTH Aachen (Germany) and with Slovak Society for Computer Science. For the ?rst time in its history, WG took place in a country of the former eastern block, in the Slovak Republic. The program committee of WG 98 consisted of: H. Bodlaender, Utrecht (NL) A. Brandst adt, Rostock (D) M. Habib, Montpellier (F) J. Hromkovi? c, Aachen (D) L. Kirousis, Patras (GR) L. Ku? cera, Praha (CR) A. Marchetti-Spaccamela, Roma (I) E. Mayr, Munc hen (D) R. Moehring, Berlin (D) M. Nagl, Aachen (D) H. Noltemeier, Wurzburg (D) F. Parisi Presicce, Roma (I) O. Syk ora, Bratislava (SK) G. Tinhofer, Munc hen (D) D. Wagner, Konstanz (D) P.

Produktdetails

• Lecture Notes in Computer Science 1517
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 10692760, 978-3-540-65195-6
• 1998.
• Seitenzahl: 404
• Erscheinungstermin: 14. Oktober 1998
• Englisch
• Abmessung: 235mm x 155mm x 22mm
• Gewicht: 523g
• ISBN-13: 9783540651956
• ISBN-10: 3540651950
• Artikelnr.: 09232054

Autorenporträt

Prof. Dr. Juraj Hromkovic war 1997 - 2003 Professor für Algorithmen und Komplexität an der RWTH Aachen. Seit Januar 2004 ist er Professor für Informatik an der ETH Zürich. Seit 2010 ist er Mitglied der Academia Europaea.

Inhaltsangabe

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width.- Minus Domination in Small-Degree Graphs.- The Vertex-Disjoint Triangles Problem.- Communication in the Two-Way Listen-in Vertex-Disjoint Paths Mode.- Broadcasting on Anonymous Unoriented Tori.- Families of Graphs Having Broadcasting and Gossiping Properties.- Optical All-to-All Communication in Inflated Networks.- A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking.- A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees.- Rankings of Directed Graphs.- Drawing Planar Partitions II: HH-Drawings.- Triangles in Euclidean Arrangements.- Internally Typed Second-Order Term Graphs.- Compact Implicit Representation of Graphs.- Graphs with Bounded Induced Distance.- Diameter Determination on Restricted Graph Families.- Independent Tree Spanners.- Upgrading Bottleneck Constrained Forests.- Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition.- Improved Compressions of Cube-Connected Cycles Networks.- Efficient Embeddings of Grids into Grids.- Integral Uniform Flows in Symmetric Networks.- Splitting Number is NP-Complete.- Tree Spanners in Planar Graphs.- A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs.- Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases.- Domination and Steiner Tree Problems on Graphs with Few P 4s.- Minimum Fill-In and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.- Interval Completion with the Smallest Max-Degree.- An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor..