Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing

DOI10.1016/S0304-3975(97)00241-7zbMath0945.68189OpenAlexW2161426837WikidataQ55952669 ScholiaQ55952669MaRDI QIDQ1575664

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00241-7

zbMATH Keywords

algorithm graph Boolean matrix partition refinement data-structure

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items (96)

An optimal algorithm to recognize Robinsonian dissimilarities ⋮ Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ Recognizing graph search trees ⋮ Can transitive orientation make sandwich problems easier? ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ On the $m$-clique free interval subgraphs polytope: polyhedral analysis and applications ⋮ Induced disjoint paths in circular-arc graphs in linear time ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ Ptolemaic and chordal cover-incomparability graphs ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Optimal interval scheduling with a resource constraint ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ Graph searches and their end vertices ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Robinsonian matrices: recognition challenges ⋮ Succinct encodings for families of interval graphs ⋮ Extending partial representations of interval graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ Fast-mixed searching and related problems on graphs ⋮ Characterizing interval graphs which are probe unit interval graphs ⋮ A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS ⋮ A general label search to investigate classical graph search algorithms ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ Linear optimization over homogeneous matrix cones ⋮ The diameter of AT‐free graphs ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ A story of diameter, radius, and (almost) Helly property ⋮ A tie-break model for graph search ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ Finding biclique partitions of co-chordal graphs ⋮ Unnamed Item ⋮ Reasoning about visibility ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Unnamed Item ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Fully dynamic representations of interval graphs ⋮ Min-Orderable Digraphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ Practical and efficient circle graph recognition ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ One-phase algorithm for the determination of minimal vertex separators of chordal graphs ⋮ List matrix partitions of graphs representing geometric configurations ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Tractability Results for the Consecutive-Ones Property with Multiplicity ⋮ Strict chordal and strict split digraphs ⋮ A REVIEW OF TREE CONVEX SETS TEST ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Minimal proper interval completions ⋮ A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Hardness results on the gapped consecutive-ones property problem ⋮ On end-vertices of lexicographic breadth first searches ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ A simple linear time algorithm for cograph recognition ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs ⋮ Fast algorithms for identifying maximal common connected sets of interval graphs ⋮ Graphs of linear clique-width at most 3 ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Minimal interval completion through graph exploration ⋮ A clique-difference encoding scheme for labelled $k$-path graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Filters for Efficient Composition of Weighted Finite-State Transducers ⋮ Witness rectangle graphs ⋮ Can Everybody Sit Closer to Their Friends Than Their Enemies? ⋮ Consecutive Ones Property Testing: Cut or Swap ⋮ Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ Phylogenetic graph models beyond trees ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ Characterizing path graphs by forbidden induced subgraphs ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ The Recognition Problem of Graph Search Trees ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Lexicographic Orientation Algorithms ⋮ A type of algebraic structure related to sets of intervals ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ A note on the consecutive ones submatrix problem. ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Computing the metric dimension for chain graphs ⋮ Fast Diameter Computation within Split Graphs ⋮ The $k$-separator problem: polyhedra, complexity and approximation results ⋮ Minimising the number of gap-zeros in binary matrices

Cites Work

This page was built for publication: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing