Publication:3883524

Publication date: 1979

matching; planar graphs; NP-completeness; connectivity; shortest paths; minimum spanning tree; planarity testing; depth- first search; optimum branching problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

68R10: Graph theory (including graph drawing) in computer science

90B10: Deterministic network models in operations research

05-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics

Related Items

On the capabilities of systolic systems, A new correctness criterion for the proof nets of non-commutative multiplicative linear logics, A bidirectional heuristic for maximizing the net present value of large-scale projects subject to limited resources, Low-connectivity network design on series-parallel graphs, Bicriteria product design optimization: An efficient solution procedure using AND/OR trees, A parallel approach to the Eulerian cycle problem, Efficient reductions of picture words, Greedy approximation algorithms for directed multicuts, A fuzzy max-flow min-cut theorem., Optimal collective dichotomous choice under partial order constraints, Communication in the two-way listen-in vertex-disjoint paths mode, The DFS-heuristic for orthogonal graph drawing, On Physical Mapping and the consecutive ones property for sparse matrices, Shuffling biological sequences, An efficient distributed algorithm for centering a spanning tree of a biconnected graph, Routing on trees, The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, On paths with the shortest average arc length in weighted graphs, A lower bound on the period length of a distributed scheduler, Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases, On the thickness of graphs of given degree, Optimal deadlock resolutions in edge-disjoint reducible wait-for graphs, Optimal covering of cacti by vertex-disjoint paths, Fusion and propagation with multiple observations in belief networks, Temporal constraint networks, Reducing conflict resolution time for solving graph problems in broadcast communications, Optimal fault-tolerant routings for connected graphs, A model classifying algorithms as inherently sequential with applications to graph searching, A new graph triconnectivity algorithm and its parallelization, Coalition formation under limited communication, An algorithm for min-cost edge-disjoint cycles and its applications, A model for determining the cost-effectiveness of T1 transmission in certain integrated networks, Polyhedron complexes with simply transitive group actions and their realizations, A minimum 3-connectivity augmentation of a graph, I/O- and CPU-optimal recognition of strongly connected components, The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm, 2-partition-transitive tournaments, Graph traversals, genes and matroids: An efficient case of the travelling salesman problem, Reliable communication over partially authenticated networks, Minimum-weight vertex cover problem for two-class resource connection graphs, Queue-mergesort, Self-stabilizing depth-first search, A logical query language for hypermedia systems, A graph approximation heuristic for the vertex cover problem on planar graphs, Heuristics for scheduling resource-constrained projects in MPM networks, A linear algorithm for centering a spanning tree of a biconnected graph, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Exact solutions for the construction of optimal length test sequences, At most single-bend embeddings of cubic graphs, Codes modulo finite monadic string-rewriting systems, Finding maximum matching for bipartite graphs in parallel, Planarity testing in parallel, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Grid embedding of 4-connected plane graphs, Partial breakdown in two-factor models, Reliability evaluation of large telecommunication networks, A greedy algorithm for the optimal basis problem, On solving intransitivities in repeated pairwise choices, A BDD SAT solver for satisfiability testing: An industrial case study, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Algorithms for area-efficient orthogonal drawing, On the complexity of specification morphisms, Farrell polynomials on graphs of bounded tree width, Decomposition of a hypergraph by partial-edge separators, Three-dimensional orthogonal graph drawing algorithms, Simple and efficient network decomposition and synchronization, Fixed-parameter complexity in AI and nonmonotonic reasoning, Backjump-based backtracking for constraint satisfaction problems, A clustering algorithm based on graph connectivity, A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs, Characterizations of consistent marked graphs, The complexity of planarity testing, Nearly sign-nonsingular matrices, Searching for acyclic orientations of graphs, The parallel complexity of growth models, Propositional semantics for disjunctive logic programs, Optimal path cover problem on block graphs, Deciding bisimilarity and similarity for probabilistic processes., Inconsistency analysis by approximately specified priorities, Graph theoretic analysis of PLA folding heuristics, Two-page book embedding of trees under vertex-neighborhood constraints, A note on rectilinear and polar visibility graphs, Decomposing toroidal graphs into circuits and edges, Orthogonal representations over finite fields and the chromatic number of graphs, Theory of computation of multidimensional entropy with an application to the monomer-dimer problem, Unnamed Item, Unnamed Item