On Comparability and Permutation Graphs
From MaRDI portal
Publication:3685215
DOI10.1137/0214048zbMath0568.68051OpenAlexW1994038277MaRDI QIDQ3685215
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214048
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (64)
A note on transitive orientations with maximum sets of sources and sinks ⋮ Coloring permutation graphs in parallel ⋮ A theorem on permutation graphs with applications ⋮ Primitive 2-structures with the \((n-2)\)-property ⋮ A \(k\)-structure generalization of the theory of 2-structures ⋮ On the feedback vertex set problem in permutation graphs ⋮ Efficient algorithms for minimum weighted colouring of some classes of perfect graphs ⋮ On the performance of the first-fit coloring algorithm on permutation graphs ⋮ Distance approximating spanning trees ⋮ FO model checking on geometric graphs ⋮ Bipartite permutation graphs ⋮ Testing superperfection of k-trees ⋮ An NC algorithm for the clique cover problem in cocomparability graphs and its application ⋮ Finding a maximum matching in a permutation graph ⋮ Stage-graph representations ⋮ Unnamed Item ⋮ Optimal channel allocation for several types of cellular radio networks ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ On the structure of trapezoid graphs ⋮ A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs ⋮ Weighted domination of cocomparability graphs ⋮ The parity path problem on some subclasses of perfect graphs ⋮ Planar stage graphs: Characterizations and applications ⋮ Drawing and encoding two-dimensional posets ⋮ On treewidth and minimum fill-in of asteroidal triple-free graphs ⋮ Parallel \(N\)-free order recognition ⋮ The firebreak problem ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Generate all maximal independent sets in permutation graphs ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Finding a maximum independent set in a permutation graph ⋮ Graphs whose complement and square are isomorphic ⋮ Characterization of 2-path signed network ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ The interval inclusion number of a partially ordered set ⋮ Treewidth and pathwidth of permutation graphs ⋮ A tight lower bound for primitivity in k-structures ⋮ Cycle-free partial orders and chordal comparability graphs ⋮ Transitive closure for restricted classes of partial orders ⋮ Finding large holes ⋮ Parallel interval order recognition and construction of interval representations ⋮ Optimal shooting: Characterizations and applications ⋮ 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 ⋮ Minimal comparability completions of arbitrary graphs ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ Maximum \(k\)-covering of weighted transitive graphs with applications ⋮ Circular permutation graph family with applications ⋮ Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs ⋮ \(O(m\log n)\) split decomposition of strongly-connected graphs ⋮ Algorithmic combinatorics based on slicing posets ⋮ On \(k\)-tree containment graphs of paths in a tree ⋮ Graph isomorphism restricted by lists ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ A new approach for the domination problem on permutation graphs ⋮ An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs ⋮ Unnamed Item ⋮ O(m logn) Split Decomposition of Strongly Connected Graphs ⋮ Modular decomposition and transitive orientation ⋮ Parallel algorithms for permutation graphs ⋮ An algorithm for minimizing setups in precedence constrained scheduling ⋮ Decomposing a set of points into chains, with applications to permutation and circle graphs
This page was built for publication: On Comparability and Permutation Graphs
