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 (only showing first 100 items - show all)

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

This page was built for publication: Transitive Orientation of Graphs and Identification of Permutation Graphs