Graph separators, with applications
This book appeared in the edition ``Frontiers of Computer Science and quite corresponds to the goal of that edition. It presents some concepts of the graph theory and then their applications in the computer science. The most important application is in the construction of VLSI-circuits (Very Large Scale Integrated circuits). But there are also other applications described.NEWLINENEWLINENEWLINEThe first chapter is ``A Technical Introduction. It explains basic concepts of the graph theory and presents some graph families which are interesting from the viewpoint of the topic of the book. The principal concept of the book follows, namely the graph separator. It is a set of vertices or a set of edges whose removal divides the graph into two or more disjoint subgraphs. Some ``variations on the theme are presented mainly the graph embeddings. (At those embeddings an edge may be transformed into a path of length greater than one.)NEWLINENEWLINENEWLINEIn the second chapter applications are described. As it was mentioned, the most important application is laying out VLSI-circuits. Other applications are the so-called nonserial dynamic programming, graph embeddings via separators, strongly universal interval hypergraphs and pebbling games. To separators and their variants always some numerical values are related and they should be maximized or minimized. This is the content of the third chapter ``Upper-Bound Techniques and of the fourth chapter ``Lower-Bound Techniques. At the end Appendix A is added; in it the authors return to the topis of the second chapter and apply the content of the third and the fourth chapter in them.NEWLINENEWLINENEWLINEThe book may be recommended mainly to computer scientists; to them it brings information about graph theory concepts which can be theoretical source of applications. Among graph theorists the book will be helpful mainly for those who study and use graph algorithms.
- An experimental evaluation of local search heuristics for graph partitioning
- The separator theorem for rooted directed vertex graphs
- Minimal congestion trees
- The size and depth of layered Boolean circuits
- Solution methods for the vertex variant of the network system vulnerability analysis problem
- Separators and adjustment sets in causal graphs: complete criteria and an algorithmic framework
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- Segre's hemisystem and McLaughlin's graph
- A near optimal algorithm for edge separators (preliminary version)
- scientific article; zbMATH DE number 4091555 (Why is no real title available?)
- scientific article; zbMATH DE number 16297 (Why is no real title available?)
- New constructions of SSPDs and their applications
- An approach to emulating separable graphs
- scientific article; zbMATH DE number 1953093 (Why is no real title available?)
- Graph layouts via layered separators
- scientific article; zbMATH DE number 867693 (Why is no real title available?)
- A new lower bound on the size of the smallest vertex separator of a graph
- On finding separators in temporal split and permutation graphs
- Finding minimum balanced separators -- an exact approach
- \(N\)-separators in planar graphs
- Embedding multidimensional grids into optimal hypercubes
This page was built for publication: Graph separators, with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2748499)
