Graph Theory and Algorithms: 17th Symposium of Research Institute of Electrical Communication, Tohoku University, Sendai, Japan, October 24-25, 1980. ProceedingsN. Saito, T. Nishizeki |
From inside the book
Results 1-5 of 7
Page
Sorry, this page's content is restricted.
Sorry, this page's content is restricted.
Page 37
Sorry, this page's content is restricted.
Sorry, this page's content is restricted.
Page 38
Sorry, this page's content is restricted.
Sorry, this page's content is restricted.
Page 39
Sorry, this page's content is restricted.
Sorry, this page's content is restricted.
Page 41
Sorry, this page's content is restricted.
Sorry, this page's content is restricted.
Contents
DIVIDING A SYSTEM INTO ALMOST UNIDIRECTIONAL BLOCKS | 1 |
A LINEAR ALGORITHM FOR FIVECOLORING A PLANAR GRAPH | 9 |
ON THE LAYERING PROBLEM OF MULTILAYER PWB WIRING | 20 |
A STATUS ON THE LINEAR ARBORICITY | 38 |
ON CENTRALITY FUNCTIONS OF A GRAPH | 45 |
CANONICAL DECOMPOSITIONS OF SYMMETRIC SUBMODULAR SYSTEMS | 53 |
THE SUBGRAPH HOMEOMORPHISM PROBLEM ON REDUCIBLE FLOW GRAPHS | 65 |
COMBINATORIAL PROBLEMS ON SERIESPARALLEL GRAPHS | 79 |
DUALITIES IN GRAPH THEORY AND IN THE RELATED FIELDS VIEWED FROM THE METATHEORETICAL STANDPOINT | 124 |
ON CENTRAL TREES OF A GRAPH | 137 |
ON POLYNOMIAL TIME COMPUTABLE PROBLEMS | 152 |
HOMOMORPHISMS OF GRAPHS AND THEIR GLOBAL MAPS | 159 |
ALGORITHMS FOR SOME INTERSECTION GRAPHS | 171 |
AN EFFICIENT ALGORITHM TO FIND A HAMILTONIAN CIRCUIT IN A 4CONNECTED MAXIMAL PLANAR GRAPH | 182 |
CHARACTERIZATION OF POLYHEX GRAPHS AS APPLIED TO CHEMISTRY | 196 |
THE TWO DISJOINT PATH PROBLEM AND WIRE ROUTING DESIGN | 207 |
A GRAPHPLANARIZATION ALGORITHM AND ITS APPLICATION TO RANDOM GRAPHS | 95 |
SOME COMMON PROPERTIES FOR REGULARIZABLE GRAPHS EDGECRITICAL GRAPHS AND BGRAPHS | 108 |
Other editions - View all
Common terms and phrases
2-connected 2-terminal graphs 2-transversal A₁ adjacency lists algorithm arcs bipartite C1 and C2 called canonical decomposition canonical decomposition tree central tree centrality function chord chordal graphs circuit color component contains corresponding critical set cutset defined Definition deletion problem denote directed graph disjoint paths dual duality electric network endpoint exists exterior face follows G₁ and G₂ G₁ into G₂ given net list graph G graph theory h₁ h₂ Hamiltonian path Hence homomorphism homomorphism of G₁ integer intersection graph interval graphs Japan Lemma Let G let h linear arboricity matrix matroids mergible minimum number N₁ node NP-complete number of edges number of vertices obtained pair planar graph polygon type polyhex polynomial PQ-tree Proof quasi-regularizable recursive regularizable respect series-parallel graph sextet st-numberings Step strongly connected graphs subset subtree graph symmetric submodular system T₁ Theorem tree of G unidirectional blocks V₁ vertex
Popular passages
Page 195 - MR GAREY, DS JOHNSON AND RE TARJAN, The planar Hamiltonian circuit problem is NP-complete, SIAM J.