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)

Periodic assignment and graph colouring ⋮ Recognition of \(d\)-dimensional Monge arrays ⋮ Algorithms for interval catch digraphs ⋮ Neighborhood perfect graphs ⋮ Arboricity and bipartite subgraph listing algorithms ⋮ A linear algorithm for embedding planar graphs using PQ-trees ⋮ Rectilinear planar layouts and bipolar orientations of planar graphs ⋮ Finding small simple cycle separators for 2-connected planar graphs ⋮ Characterizations of two classes of digraphs ⋮ Finding the minimum bandwidth of an interval graph ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ Planarity testing in parallel ⋮ Bipartite permutation graphs ⋮ Finding minimum height elimination trees for interval graphs in polynomial time ⋮ Testing a mixture model of single-peaked preferences ⋮ Graph graphics: Theory and practice ⋮ On-line sorting of twisted sequences in linear time ⋮ Testing for class membership in multi-parent hierarchies ⋮ The maximum k-colorable subgraph problem for chordal graphs ⋮ Proper interval graphs and the guard problem ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ On the domatic number of interval graphs ⋮ A unified approach to domination problems on interval graphs ⋮ Total domination in interval graphs revisited ⋮ An efficient parallel algorithm for planarity ⋮ Restrictions of minimum spanner problems ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ On minimum intersection of two minimum dominating sets of interval graphs ⋮ Recognizing single-peaked preferences on a tree ⋮ Recognition of Robinsonian dissimilarities ⋮ Secure domination in proper interval graphs ⋮ Unit disk graph recognition is NP-hard ⋮ New results on drawing angle graphs ⋮ Satisfiability problems on intervals and unit intervals ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ An efficient PQ-graph algorithm for solving the graph-realization problem ⋮ A monadic second-order definition of the structure of convex hypergraphs. ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ PC trees and circular-ones arrangements. ⋮ A simple algorithm for finding a cycle of length greater than three and without diagonals ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ A large set of torus obstructions and how they were discovered ⋮ On minimal augmentation of a graph to obtain an interval graph ⋮ Optimal packing and covering in the plane are NP-complete ⋮ Local and union boxicity ⋮ Fully dynamic representations of interval graphs ⋮ On the thickness of graphs of given degree ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Algorithmic aspects of semitotal domination in graphs ⋮ Optimal canonization of all substrings of a string ⋮ On finding the minimum bandwidth of interval graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Finding a potential community in networks ⋮ On the classes of interval graphs of limited nesting and count of lengths ⋮ The eternal dominating set problem for interval graphs ⋮ List matrix partitions of graphs representing geometric configurations ⋮ Dynamic monopolies for interval graphs with bounded thresholds ⋮ A simple algorithm for secure domination in proper interval graphs ⋮ Simultaneous embedding: edge orderings, relative positions, cutvertices ⋮ A new characterization of proper interval graphs ⋮ Processor optimization for flow graphs ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Hardness results on the gapped consecutive-ones property problem ⋮ Optimal linear arrangements using betweenness variables ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Paths in interval graphs and circular arc graphs ⋮ Computing the branchwidth of interval graphs ⋮ Polynomial and APX-hard cases of the individual haplotyping problem ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ One more polynomial complete consecutive retrieval problem ⋮ A recognition algorithm for the intersection graphs of paths in trees ⋮ Representing triangulated graphs in stars ⋮ A note on the Hamiltonian circuit problem on directed path graphs ⋮ A fast bipartite network flow algorithm for selective assembly ⋮ Phylogenetic graph models beyond trees ⋮ On the complexity of the k-chain subgraph cover problem ⋮ A polynomially solvable class of quadratic semi-assignment problems ⋮ On testing consecutive-ones property in parallel ⋮ On probe interval graphs ⋮ On the consecutive ones property ⋮ Distance paired-domination problems on subclasses of chordal graphs ⋮ Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms ⋮ A selected tour of the theory of identification matrices ⋮ Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing ⋮ On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Computational implementation of Fujishige's graph realizability algorithm ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ Modular decomposition and transitive orientation ⋮ Matrix sandwich problems ⋮ On counting planar embeddings ⋮ A fast algorithm for maximum integral two-commodity flow in planar graphs ⋮ Finding Hamiltonian circuits in interval graphs ⋮ A genetic algorithm for determining the thickness of a graph ⋮ Recognition algorithm for intersection graphs of edge disjoint paths in a tree ⋮ Interval graphs and maps of DNA ⋮ Reconstruction graphs and testing their properties in a relational spatial database ⋮ Finding the closed partition of a planar graph ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar 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