Transitive Orientation of Graphs and Identification of Permutation Graphs

DOI10.4153/CJM-1971-016-5zbMath0204.24604MaRDI QIDQ5602691

Amir Pnueli, Shimon Even, Abraham Lempel

Publication date: 1971

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Related Items

Permutation graphs and the weak Bruhat order, Testing superperfection of k-trees, Computing the all-pairs longest chains in the plane, On Strict (Outer-)Confluent Graphs, MaxCut on permutation graphs is NP‐complete, Computation of diameter, radius and center of permutation graphs, A compact data structure and parallel algorithms for permutation graphs, Multipermutations and Stirling multipermutations, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree, Vertex deletion into bipartite permutation graphs, Coloring permutation graphs in parallel, A theorem on permutation graphs with applications, Compatibility between interval structures and partial orderings, On the feedback vertex set problem in permutation graphs, Strengthened 0-1 linear formulation for the daily satellite mission planning, On the performance of the first-fit coloring algorithm on permutation graphs, Exploring the concept of perfection in 3-hypergraphs, Bipartite permutation graphs, On two-processor scheduling and maximum matching in permutation graphs, Coloration de graphes : fondements et applications, On domination problems for permutation and other graphs, On containment graphs of paths in a tree, Finding a maximum matching in a permutation graph, Stage-graph representations, Double-threshold permutation graphs, Vertex deletion into bipartite permutation graphs, Algorithmic aspects of intersection graphs and representation hypergraphs, String graphs. I: The number of critical nonstring graphs is infinite, On orientations and shortest paths, Transitive oriented 3 hypergraphs of cyclic orders, Complete edge-colored permutation graphs, A recognition algorithm for simple-triangle graphs, Planar stage graphs: Characterizations and applications, Parallel \(N\)-free order recognition, On the computational complexity of ordered subgraph recognition, Domination in transitive colorings of tournaments, On the intersection of tolerance and cocomparability graphs, Generate all maximal independent sets in permutation graphs, Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs, The mutual exclusion scheduling problem for permutation and comparability graphs., Succinct permutation graphs, Erratum and addendum to ``A linear time algorithm for finding all hinge vertices of a permutation graph, Algorithms for maximumk-colorings andk-coverings of transitive graphs, On strict (outer-)confluent graphs, On the domination number of permutation graphs and an application to strong fixed points, Partial characterizations of circle graphs, Finding a maximum independent set in a permutation graph, Hereditary dominating pair graphs, Partitioned probe comparability graphs, Stack sortable permutations, Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem, Comparability graphs and intersection graphs, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, Representations of graphs and networks (coding, layouts and embeddings), Connected permutation graphs, Track assignment, Transitive closure for restricted classes of partial orders, A condition for a family of triangles to be orientable to a cyclic order, On graphs associated to sets of rankings, New clique and independent set algorithms for circle graphs, A linear time algorithm for finding all hinge vertices of a permutation graph, An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs, Solving the shortest-paths problem on bipartite permutation graphs efficiently, Parallel interval order recognition and construction of interval representations, Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs, The weighted maximum independent set problem in permutation graphs, Constructing a stochastic critical path network given the slacks: Representation, Recent results on containment graphs of paths in a tree, Thresholds for classes of intersection graphs, On probe permutation graphs, Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs, Embedding linear orders in grids, A recognition algorithm for the intersection graphs of directed paths in directed trees, Zur Vorgabe gerichteter Kanten von Vergleichbarkeitsgraphen, Acyclic orientations of a graph and the chromatic and independence numbers, Operations on permutations and representation in graph form, Comparability graphs and a new matroid, The complexity of comparability graph recognition and coloring, Algorithms on clique separable graphs, Approximation of the double traveling salesman problem with multiple stacks, Minimum 2-tuple dominating set of permutation graphs, A polynomial-time algorithm for the paired-domination problem on permutation graphs, A recognition algorithm for the intersection graphs of paths in trees, A new approach for the domination problem on permutation graphs, Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs, Using dual network bounds in algorithms for solving generalized set packing/partitioning problems, Algorithm for the vertex packing problem, Finding maximum cliques in circle graphs, On testing isomorphism of permutation graphs, Maximum weightk-independent set problem on permutation graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, \(k\)-majority digraphs and the hardness of voting with a constant number of voters, Sorting by bounded block-moves, An efficient algorithm to find next-to-shortest path on permutation graphs, A New Perspective on the Mereotopology of RCC8., The Complexity of the Partial Order Dimension Problem, Lexicographic Orientation Algorithms, Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets, Circular permutation graphs, Modular decomposition and transitive orientation, An algorithm for constructing edge-trees from hypergraphs, Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks, On realizable biorders and the biorder dimension of a relation, Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs, Parallel algorithms for permutation graphs, On maximum independent set of categorical product and ultimate categorical ratios of graphs, Minimum r-neighborhood covering set of permutation graphs, Orientations of circle graphs, Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index)