Permutation Graphs and Transitive Graphs

DOI10.1145/321707.321710zbMath0251.05113OpenAlexW2022971294WikidataQ56210403 ScholiaQ56210403MaRDI QIDQ5663894

Shimon Even, Abraham Lempel, Amir Pnueli

Publication date: 1972

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321707.321710

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Permutation graphs and the weak Bruhat order, Orienting graphs to optimize reachability, A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders, Bipartite permutation graphs, Computing a dominating pair in an asteroidal triple-free graph in linear time, Computing the all-pairs longest chains in the plane, Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, On domination problems for permutation and other graphs, 2-nested matrices: towards understanding the structure of circle graphs, Trapezoid graphs and their coloring, Algorithmic aspects of intersection graphs and representation hypergraphs, A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs, Two characterisations of the minimal triangulations of permutation graphs, Scheduling jobs within time windows on identical parallel machines: New model and algorithms, Permutation bigraphs and interval containments, The Complexity of the Partial Order Dimension Problem: Closing the Gap, Asteroidal triple-free graphs, An algorithm for generating all maximal independent subsets of posets, Multipermutations and Stirling multipermutations, On linear and circular structure of (claw, net)-free graphs, On the domination number of permutation graphs and an application to strong fixed points, Finding a maximum independent set in a permutation graph, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, Comparability graphs and intersection graphs, Dominating sets in perfect graphs, Representations of graphs and networks (coding, layouts and embeddings), Treewidth and pathwidth of permutation graphs, 3D-interval-filament graphs, 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, A linear time algorithm to compute a dominating path in an AT-free graph, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, On a graph partition problem with application to VLSI layout, Minimum weight feedback vertex sets in circle graphs, Competition-reachability of a graph, Counting maximal independent sets in directed path graphs, Some simplified NP-complete graph problems, A Note on k-Colorability of P 5-Free Graphs, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Operations on permutations and representation in graph form, Intersection graphs of curves in the plane, Comparability graphs and a new matroid, Efficient Algorithms for (3,1) Graphs, The complexity of comparability graph recognition and coloring, On random trees obtained from permutation graphs, On finding separators in temporal split and permutation graphs, On finding separators in temporal split and permutation graphs, The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs, Circular permutation graphs, Fully dynamic algorithms for permutation graph coloring, Efficient Local Representations of Graphs, Forbidden induced subgraph characterization of circle graphs within split graphs, Graph Classes and Forbidden Patterns on Three Vertices, The Dimension of a Comparability Graph, Decomposing a set of points into chains, with applications to permutation and circle graphs, Orientations of circle graphs