177,301 research outputs found
Graph Algorithms and Applications 2
No full textThis book contains Volumes 4 and 5 of the Journal of Graph Algorithms and Applications (JGAA). The first book of this series, Graph Algorithms and Applications 1, published in March 2002, contains Volumes 1–3 of JGAA.
JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design. The journal is supported by distinguished advisory and editorial boards, has high scientific standards, and takes advantage of current electronic document technology. The electronic version of JGAA is available on the Web at http://jgaa.info/.
Graph Algorithms and Applications 2 presents contributions from prominent authors and includes selected papers from the Dagstuhl Seminar on Graph Algorithms and Applications and the Symposium on Graph Drawing in 1998. All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Approximations of Weighted Independent Set and Hereditary Subset Problems (M M Halldórsson)
* Approximation Algorithms for Some Graph Partitioning Problems (G He et al.)
* Geometric Thickness of Complete Graphs (M B Dillencourt et al.)
* Techniques for the Refinement of Orthogonal Graph Drawings (J M Six et al.)
* Navigating Clustered Graphs Using Force-Directed Methods (P Eades & M L Huang)
* Clustering in Trees: Optimizing Cluster Sizes and Number of Subtrees (S E Hambrusch et al.)
* Planarizing Graphs — A Survey and Annotated Bibliography (A Liebers)
* Fully Dynamic 3-Dimensional Orthogonal Graph Drawing (M Closson et al.)
* 1-Bend 3-D Orthogonal Box-Drawings: Two Open Problems Solved (T Biedl)
* Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems (R Bar-Yehuda et al.)
* New Bounds for Oblivious Mesh Routing (K Iwama et al.)
* Connectivity of Planar Graphs (H de Fraysseix & P O de Mendez)
* and other paper
Algorithms for Plane Representations of Acyclic Digraphs
No full textAbstractAcyclic digraphs are widely used for representing hierarchical structures. Examples include PERT networks, subroutine-call graphs, family trees, organization charts, Hasse diagrams, and ISA hierarchies in knowledge representation diagrams. We investigate the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top. Three plane representations are considered: straight drawings, visibility representations, and grid drawings. We provide efficient algorithms that construct these representations with all edges flowing in the same direction. The time complexity is O(n) for visibility representations and grid drawings, and O(n log n) for straight drawings, where n is the number of vertices of the digraph. For covering digraphs of lattices, the complexity of constructing straight drawings is O(n). We also show that the planar digraphs that admit any one of these representations are exactly the subgraphs of planar st-graphs
Robust Proximity Queries: An Illustration of Degree-driven Algorithms Design
No full textIn the context of methodologies intended to confer robustness to geometric algorithms,
we elaborate on the exact-computation paradigm and formalize the notion of degree of a
geometric algorithm as a worst-case quantification of the precision (number of bits) to which arithmetic
calculation have to be executed in order to guarantee topological correctness. We also propose
a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm
and an illustration of our general approach where algorithm design is driven also by the degree,
we consider the important classical problem of proximity queries in two and three dimensions and
develop a new technique for the efficient and robust execution of such queries based on an implicit
representation of Voronoi diagrams. Our new technique offers both low degree and fast query time
and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number
of operations, and arithmetic degree
Graph ALgorithms and Applications 4
No full textThis book contains Volume 7 of the Journal of Graph Algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design.
Graph Algorithms and Applications 4 presents contributions from prominent authors and includes selected papers from (a) the Seventh International Workshop on Algorithms and Data Structures (WADS 2001) and (b) the 2001 Symposium on Graph Drawing (GD 2001). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry (C Barrett et al.)
* On External-Memory Planar Depth First Search (L Arge et al.)
* Finding Shortest Paths with Computational Geometry (P-S Loh)
* Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution (C Duncan & S Kobourov)
* and other paper
Graph Algorihms and Applications 3
No full textThis book contains Volume 6 of the Journal of Graph Algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design.
Graph Algorithms and Applications 3 presents contributions from prominent authors and includes selected papers from the Symposium on Graph Drawing (1999 and 2000). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Triangle-Free Planar Graphs and Segment Intersection Graphs (N de Castro et al.)
* Traversing Directed Eulerian Mazes (S Bhatt et al.)
* A Fast Multi-Scale Method for Drawing Large Graphs (D Harel & Y Koren)
* GRIP: Graph Drawing with Intelligent Placement (P Gajer & S G Kobourov)
* Graph Drawing in Motion (C Friedrich & P Eades)
* A 6-Regular Torus Graph Family with Applications to Cellular and Interconnection Networks (M Iridon & D W Matula)
* and other paper
Collision-induced radio-frequency transitions in CH3I
No full textThe highly sensitive method of radio-frequency-infrared double resonance inside a CO2 laser is applied to study collision-induced transitions in CH3I in a four-level double resonance scheme. Pure nuclear quadrupole resonances are observed as the result of collision population transfer between different rotational levels. The intensity ratios of the collision-induced dips to the corresponding three-level double resonance signals are measured for a number of transitions in the ground and excited vibrational states. Collision selection rules in the pure gas and in mixtures with polar and non-polar gases are discussed
- …
