Bipartite permutation graphs
From MaRDI portal
It is shown that bipartite permutation graphs have good algorithmic properties in contrast to general bipartite or permutation graphs. Two characterizations of these graphs are presented which lead to a linear time recognition algorithm and also to polynomial algorithms for Hamiltonian problems, a variant of the crossing number problem and the minimum fill-in problem on these graphs.
Recommendations
Cites work
- A Characterization of Comparability Graphs and of Interval Graphs
- A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Computing the Minimum Fill-In is NP-Complete
- Domination in permutation graphs
- Finding minimum dominating cycles in permutation graphs
- Graph theory
- Hamilton Paths in Grid Graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3900817 (Why is no real title available?)
- scientific article; zbMATH DE number 3943870 (Why is no real title available?)
- scientific article; zbMATH DE number 3694608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3310759 (Why is no real title available?)
- On Comparability and Permutation Graphs
- On testing isomorphism of permutation graphs
- Permutation Graphs and Transitive Graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The complexity of comparability graph recognition and coloring
- The NP-completeness column: an ongoing guide
- The NP-completeness column: An ongoing guide
- The NP-completeness column: An ongoing guide
- Transitiv orientierbare Graphen
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Triangulated graphs and the elimination process
Cited in
(only showing first 100 items - show all)- Labeling bipartite permutation graphs with a condition at distance two
- Bandwidth of bipartite permutation graphs in polynomial time
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- On domination problems for permutation and other graphs
- The weighted maximum independent set problem in permutation graphs
- Optimal path cover problem on block graphs and bipartite permutation graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
- Mutual placement of bipartite graphs
- Line directionality of orders
- Parallel algorithms for permutation graphs
- A theorem on permutation graphs with applications
- Weighted efficient domination problem on some perfect graphs
- Partitioning graphs into Hamiltonian ones
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Triangulating multitolerance graphs
- On the \(k\)-path partition of graphs.
- On the approximability of average completion time scheduling under precedence constraints.
- Induced matchings in asteroidal triple-free graphs
- Biconvex graphs: Ordering and algorithms
- A new lower bound for the bipartite crossing number with applications
- Coloring permutation graphs in parallel
- Linear-time algorithms for counting independent sets in bipartite permutation graphs
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Interval \(k\)-graphs and orders
- Algorithmic aspects of bipartite graphs
- Bipartite-perfect graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- Permuting matrices to avoid forbidden submatrices
- On the recognition of permuted bottleneck Monge matrices
- On edge perfectness and classes of bipartite graphs
- HAMILTONian circuits in chordal bipartite graphs
- Perspectives of Monge properties in optimization
- Optimal computation of shortest paths on doubly convex bipartite graphs
- Graph isomorphism and identification matrices: Sequential algorithms
- Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
- \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
- The maximum binary tree problem
- On list \(k\)-coloring convex bipartite graphs
- 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
- Coloring a dominating set without conflicts: \(q\)-subset square coloring
- Double-threshold permutation graphs
- Vertex deletion into bipartite permutation graphs
- Biclique graphs of interval bigraphs
- Parikh word representability of bipartite permutation graphs
- Stick graphs with length constraints
- Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
- On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
- A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
- Algorithm and hardness results on hop domination in graphs
- Graphs and digraphs represented by intervals and circular arcs
- Linear structure of bipartite permutation graphs and the longest path problem
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Biclique graph of bipartite permutation graphs
- Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
- A dichotomy for minimum cost graph homomorphisms
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- Acyclically pushable bipartite permutation digraphs: an algorithm
- Complexity of Hamiltonian cycle reconfiguration
- Succinct permutation graphs
- On permutations avoiding partially ordered patterns defined by bipartite graphs
- Bipartite-perfect graphs
- Minimum cost homomorphisms with constrained costs
- A faster fixed parameter algorithm for two-layer crossing minimization
- Permutation-exchange graphs that emulate the binary cube
- Computing the cutwidth of bipartite permutation graphs in linear time
- On computing longest paths in small graph classes
- Bipartite Permutation Graphs Are Reconstructible
- A polynomial time algorithm for longest paths in biconvex graphs
- Uniquely restricted matchings in interval graphs
- On the OBDD representation of some graph classes
- Ferrers dimension of grid intersection graphs
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Core and Conditional Core Path of Specified Length in Special Classes of Graphs
- Random Generation and Enumeration of Bipartite Permutation Graphs
- scientific article; zbMATH DE number 3919840 (Why is no real title available?)
- scientific article; zbMATH DE number 4063153 (Why is no real title available?)
- Permutation bigraphs and interval containments
- Random generation and enumeration of bipartite permutation graphs
- Generate all maximal independent sets in permutation graphs
- Bandwidth of convex bipartite graphs and related graphs
- scientific article; zbMATH DE number 1156661 (Why is no real title available?)
- On factorial properties of chordal bipartite graphs
- scientific article; zbMATH DE number 2076924 (Why is no real title available?)
- An attractive class of bipartite graphs
- Recognition and combinatorial optimization algorithms for bipartite chain graphs
- How to use the minimal separators of a graph for its chordal triangulation
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- Acyclic matchings in subclasses of bipartite graphs
- Circularly compatible ones, D-circularity, and proper circular-arc bigraphs
- Crossing Layout in Non-planar Graph Drawings
- Rainbow vertex coloring bipartite graphs and chordal graphs
- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
- Labelled well-quasi-order for permutation classes
- On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Bipartite Analogues of Comparability and Cocomparability Graphs
This page was built for publication: Bipartite permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1092931)
