Bipartite permutation graphs

DOI10.1016/S0166-218X(87)80003-3zbMath0628.05055MaRDI QIDQ1092931

Andreas Brandstädt, Lorna K. Stewart, Jeremy P. Spinrad

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphHamiltonian cyclecrossing numberpermutation graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99) Eulerian and Hamiltonian graphs (05C45)

Related Items (only showing first 100 items - show all)

Coloring permutation graphs in parallel ⋮ A theorem on permutation graphs with applications ⋮ A faster fixed parameter algorithm for two-layer crossing minimization ⋮ Cyclability in graph classes ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Weighted efficient domination problem on some perfect graphs ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Acyclic domination on bipartite permutation graphs ⋮ Linear structure of bipartite permutation graphs and the longest path problem ⋮ The rook problem on saw-toothed chessboards ⋮ On the OBDD representation of some graph classes ⋮ The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs ⋮ On domination problems for permutation and other graphs ⋮ On the recognition of permuted bottleneck Monge matrices ⋮ Double-threshold permutation graphs ⋮ Ferrers dimension of grid intersection graphs ⋮ Vertex deletion into bipartite permutation graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ Recognizing interval digraphs and interval bigraphs in polynomial time ⋮ On orthogonal ray graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ HAMILTONian circuits in chordal bipartite graphs ⋮ Perspectives of Monge properties in optimization ⋮ Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ Biclique graph of bipartite permutation graphs ⋮ Biclique graphs of interval bigraphs ⋮ Parikh word representability of bipartite permutation graphs ⋮ Triangulating multitolerance graphs ⋮ Alternating sign matrices, related (0,1)-matrices, and the Smith normal form ⋮ Permutation bigraphs and interval containments ⋮ \(L(0,1)\)-labelling of permutation graphs ⋮ Generate all maximal independent sets in permutation graphs ⋮ On the \(k\)-path partition of graphs. ⋮ Random generation and enumeration of bipartite permutation graphs ⋮ Succinct permutation graphs ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Stick graphs with length constraints ⋮ Induced matchings in asteroidal triple-free graphs ⋮ On factorial properties of chordal bipartite graphs ⋮ \(L(2,1)\)-labeling of perfect elimination bipartite graphs ⋮ Finding a maximum independent set in a permutation graph ⋮ On opposition graphs, coalition graphs, and bipartite permutation graphs ⋮ Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Edge domination on bipartite permutation graphs and cotriangulated graphs ⋮ Efficient parallel algorithms for doubly convex-bipartite graphs ⋮ Solving the shortest-paths problem on bipartite permutation graphs efficiently ⋮ ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ Visibility graphs of towers ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ Bipartite permutation graphs with application to the minimum buffer size problem ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ The weighted maximum independent set problem in permutation graphs ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization ⋮ \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs ⋮ Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time ⋮ Core and Conditional Core Path of Specified Length in Special Classes of Graphs ⋮ Interval \(k\)-graphs and orders ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ The maximum binary tree problem ⋮ A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs ⋮ A linear edge kernel for two-layer crossing minimization ⋮ Optimal path cover problem on block graphs and bipartite permutation graphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ A new approach for the domination problem on permutation graphs ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs ⋮ Labeling bipartite permutation graphs with a condition at distance two ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs ⋮ Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms ⋮ Biconvex graphs: Ordering and algorithms ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ A new lower bound for the bipartite crossing number with applications ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs ⋮ Crossing Layout in Non-planar Graph Drawings ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ A polynomial kernel for bipartite permutation vertex deletion ⋮ Algorithm and hardness results on hop domination in graphs ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ Line directionality of orders ⋮ Parallel algorithms for permutation graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Graphs and digraphs represented by intervals and circular arcs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding minimum dominating cycles in permutation graphs
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• The complexity of comparability graph recognition and coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Triangulated graphs and the elimination process
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• The NP-completeness column: an ongoing guide
• On testing isomorphism of permutation graphs
• Computing the Minimum Fill-In is NP-Complete
• Hamilton Paths in Grid Graphs
• Transitiv orientierbare Graphen
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide

This page was built for publication: Bipartite permutation graphs