Graph Theory and Algorithms: 17th Symposium of Research Institute of Electrical Communication, Tohoku University, Sendai, Japan, October 24-25, 1980. ProceedingsN. Saito, T. Nishizeki Springer Science & Business Media, 1981 - 216 sider |
Innhold
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 |
Andre utgaver - Vis alle
Vanlige uttrykk og setninger
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
Populære avsnitt
Side 195 - MR GAREY, DS JOHNSON AND RE TARJAN, The planar Hamiltonian circuit problem is NP-complete, SIAM J.