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

DOI10.1016/S0022-0000(76)80045-1zbMath0367.68034WikidataQ55952666 ScholiaQ55952666MaRDI QIDQ1242450

Kellogg S. Booth, George S. Lueker

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Trees (05C05) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

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

An optimal algorithm to recognize Robinsonian dissimilarities ⋮ CPG graphs: some structural and hardness results ⋮ Cyclability in graph classes ⋮ The recognition of geodetically connected graphs ⋮ Common intervals of trees ⋮ Consecutive retrieval property -- revisited ⋮ Edge intersection graphs of \(L\)-shaped paths in grids ⋮ Chronological rectangle digraphs ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Optimal interval scheduling with a resource constraint ⋮ Max point-tolerance graphs ⋮ On recognition of threshold tolerance graphs and their complements ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Recognizing graphs without asteroidal triples ⋮ Reconstruction of interval graphs ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Recognition and characterization of chronological interval digraphs ⋮ An improved algorithm for the red-blue hitting set problem with the consecutive ones property ⋮ A characterization of the single-peaked domain ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ A new perspective on clustered planarity as a combinatorial embedding problem ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ Edge search number of cographs ⋮ The firefighter problem on graph classes ⋮ The shield that never was: societies with single-peaked preferences are more open to manipulation and control ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ Reasoning about visibility ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ Almost every graph is divergent under the biclique operator ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Linear algorithm for optimal path cover problem on interval graphs ⋮ Backup 2-center on interval graphs ⋮ \(L(2,1)\)-labeling of perfect elimination bipartite graphs ⋮ An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals ⋮ Subgraphs of 4-regular planar graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Domination in convex and chordal bipartite graphs ⋮ Bipartite graphs, upward drawings, and planarity ⋮ A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix ⋮ An optimal greedy heuristic to color interval graphs ⋮ New sequential and parallel algorithms for interval graph recognition ⋮ A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class ⋮ Certifying algorithms ⋮ 2-layer right angle crossing drawings ⋮ On the bend-number of planar and outerplanar graphs ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution ⋮ Interval graph representation with given interval and intersection lengths ⋮ Minimal obstructions for partial representations of interval graphs ⋮ \texttt{PQser:} a Matlab package for spectral seriation ⋮ Finding outer-connected dominating sets in interval graphs ⋮ A linear-time algorithm for proper interval graph recognition ⋮ Simple linear time recognition of unit interval graphs ⋮ A linear-time algorithm for drawing a planar graph on a grid ⋮ The list distinguishing number equals the distinguishing number for interval graphs ⋮ Bipartite permutation graphs with application to the minimum buffer size problem ⋮ A branch-and-cut approach to the crossing number problem ⋮ Benders decomposition for set covering problems. Almost satisfying the consecutive ones property ⋮ Strict chordal and strict split digraphs ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ Counting endpoint sequences for interval orders and interval graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Fixed-parameter complexity of minimum profile problems ⋮ Interval competition graphs of symmetric digraphs ⋮ Strip planarity testing for embedded planar graphs ⋮ Extending partial representations of proper and unit interval graphs ⋮ Upward drawings of triconnected digraphs. ⋮ Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings ⋮ On counting interval lengths of interval graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Approximation algorithm for coloring of dotted interval graphs ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Common intervals of multiple permutations ⋮ On probe permutation graphs ⋮ Branchwidth of chordal graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ A new characterization of matrices with the consecutive ones property ⋮ Computing compatible tours for the symmetric traveling salesman problem ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Consecutive block minimization is 1.5-approximable ⋮ Labelling algorithms for paired-domination problems in block and interval graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ On compact and efficient routing in certain graph classes ⋮ Recognizing edge clique graphs among interval graphs and probe interval graphs ⋮ Preemptive scheduling and antichain polyhedra ⋮ The neighbour-scattering number can be computed in polynomial time for interval graphs ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Algorithms for maximum independent set in convex bipartite graphs ⋮ Testing planarity of geometric automorphisms in linear time ⋮ Red-blue covering problems and the consecutive ones property ⋮ The simultaneous consecutive ones problem ⋮ The clique-separator graph for chordal graphs ⋮ Recognizing graphs with fixed interval number is NP-complete ⋮ A nonfactorial algorithm for testing isomorphism of two graphs ⋮ Circular representation problem on hypergraphs ⋮ On the isomorphism problem for Helly circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• An algorithm for testing chordality of graphs
• Computing an st-numbering
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Gaussian elimination is not optimal
• A structure theorem for the consecutive 1's property
• Triangulated graphs and the elimination process
• Matrix characterizations of circular-arc graphs
• Optimal scheduling for two-processor systems
• Representation of a finite graph by a set of intervals on the real line
• Efficient Planarity Testing
• Scheduling Graphs on Two Processors
• Algorithmic Aspects of Vertex Elimination on Graphs
• Combinatorial Configurations
• File organization
• A Characterization of Comparability Graphs and of Interval Graphs

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