Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cites Work

Cited In (only showing first 100 items - show all)

Algorithmic aspects of clique-transversal and clique-independent sets
Elimination of local bridges
On the isomorphism problem for Helly circular-arc graphs
An optimal algorithm to recognize Robinsonian dissimilarities
Detecting fixed patterns in chordal graphs in polynomial time
Decomposition of integer matrices and multileaf collimator sequencing
Backup 2-center on interval graphs
Interval graph representation with given interval and intersection lengths
NP-completeness results for edge modification problems
Linear-time recognition of Helly circular-arc models and graphs
Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
Algorithms for interval catch digraphs
Simple linear time recognition of unit interval graphs
Linear time algorithms for dominating pairs in asteroidal triple-free graphs
On coalescence analysis using genealogy rooted trees
Edge intersection graphs of \(L\)-shaped paths in grids
Linear algorithm for optimal path cover problem on interval graphs
Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
Finding Hamiltonian circuits in proper interval graphs
A linear algorithm for embedding planar graphs using PQ-trees
Modular decomposition and transitive orientation
Periodic assignment and graph colouring
Proper interval graphs and the guard problem
Recognition of Robinsonian dissimilarities
Unit disk graph recognition is NP-hard
The recognition of geodetically connected graphs
Consecutive retrieval property -- revisited
2-layer right angle crossing drawings
Efficient algorithms for inferring evolutionary trees
Tractabilities and intractabilities on geometric intersection graphs
Bipartite permutation graphs
Threshold tolerance graphs
A linear-time algorithm for drawing a planar graph on a grid
On computing longest paths in small graph classes
Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
Graph classes with structured neighborhoods and algorithmic applications
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
On the \(k\)-coloring of intervals
Domination in convex and chordal bipartite graphs
Linear-time algorithm for the paired-domination problem in convex bipartite graphs
Maximum planar subgraphs and nice embeddings: Practical layout tools
Biclique graphs and biclique matrices
Rectilinear planar layouts and bipolar orientations of planar graphs
The maximum k-colorable subgraph problem for chordal graphs
The clique-separator graph for chordal graphs
Chronological rectangle digraphs
Largest chordal and interval subgraphs faster than \(2^n\)
The shield that never was: societies with single-peaked preferences are more open to manipulation and control
Bipartite graphs, upward drawings, and planarity
Computing a minimum outer-connected dominating set for the class of chordal graphs
Bipartite permutation graphs with application to the minimum buffer size problem
Recognition and characterization of chronological interval digraphs
A recognition algorithm for the intersection graphs of paths in trees
Optimal greedy algorithms for indifference graphs
Interval bigraphs and circular arc graphs
On the bend-number of planar and outerplanar graphs
Finding minimum height elimination trees for interval graphs in polynomial time
On Robinsonian dissimilarities, the consecutive ones property and latent variable models
Optimal interval scheduling with a resource constraint
On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
A review of tree convex sets test
An optimal greedy heuristic to color interval graphs
Quasi-threshold graphs
Max point-tolerance graphs
On recognition of threshold tolerance graphs and their complements
Labelling algorithms for paired-domination problems in block and interval graphs
Drawing planar graphs using the canonical ordering
Intersection graphs of Helly families of subtrees
A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
Finding Hamiltonian circuits in interval graphs
Certifying algorithms
Edge-intersection graphs of grid paths: the bend-number
\texttt{PQser:} a Matlab package for spectral seriation
A polynomially solvable class of quadratic semi-assignment problems
A simpler linear-time recognition of circular-arc graphs
A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
Weighted independent perfect domination on cocomparability graphs
Recognition of \(d\)-dimensional Monge arrays
Network construction with ordered constraints
Characterizations and recognition of circular-arc graphs and subclasses: a survey
Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
A unified approach to domination problems on interval graphs
Optimal packing and covering in the plane are NP-complete
Efficient algorithms for interval graphs and circular-arc graphs
Characterizing path graphs by forbidden induced subgraphs
The conditional covering problem on unweighted interval graphs with nonuniform coverage radius
Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
New results on induced matchings
Permuting matrices to avoid forbidden submatrices
Efficient algorithms for centers and medians in interval and circular-arc graphs
Normal Helly circular-arc graphs and its subclasses
Graph graphics: Theory and practice
Robinsonian matrices: recognition challenges
On compiling structured CNFs to OBDDs
CPG graphs: some structural and hardness results
Satisfiability problems on intervals and unit intervals
Minimax problems with bitonic matrices
A new characterization of matrices with the consecutive ones property
A faster algorithm for finding minimum Tucker submatrices

This page was built for publication: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1242450)