Bipartite permutation graphs

From MaRDI portal

Publication:1092931

Jump to:navigation, search

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 graph Hamiltonian cycle crossing number permutation 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

Permutation graphs and the weak Bruhat order, Labelled well-quasi-order for permutation classes, On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, Colouring a dominating set without conflicts: \(q\)-subset square colouring, Recognizing interval bigraphs by forbidden patterns, Critical properties of bipartite permutation graphs, Path eccentricity of graphs, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, Bipartite Analogues of Comparability and Cocomparability Graphs, The Maximum Binary Tree Problem., Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, Star Partitions of Perfect Graphs, Vertex deletion into bipartite permutation graphs, On the complexity of the maximum biplanar subgraph problem, Recognition and drawing of stick graphs, Quasimonotone graphs, Graph classes and the switch Markov chain for matchings, Posets and VPG graphs, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Transversals of longest paths, Counting Perfect Matchings and the Switch Chain, Graph Classes and Forbidden Patterns on Three Vertices, Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs, Linear-time recognition of double-threshold graphs, 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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1092931&oldid=13119303"