PC trees and circular-ones arrangements.
From MaRDI portal
Publication:1401263
DOI10.1016/S0304-3975(02)00435-8zbMATH Open1044.68125OpenAlexW1971080253MaRDI QIDQ1401263FDOQ1401263
Authors: D. Massart 
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00435-8
Recommendations
Cites Work
- Introduction to algorithms
- Title not available (Why is that?)
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Incidence matrices and interval graphs
- Transitiv orientierbare Graphen
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Decomposition of Directed Graphs
- Title not available (Why is that?)
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- A Simple Test for the Consecutive Ones Property
- A new planarity test
- Title not available (Why is that?)
- Theory of 2-structures. II: Representation through labeled tree families
- Title not available (Why is that?)
- An efficient parallel algorithm for planarity
- Title not available (Why is that?)
Cited In (39)
- Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
- Planarity algorithms via PQ-trees (extended abstract)
- An improved algorithm for the red-blue hitting set problem with the consecutive ones property
- Tree-representation of set families and applications to combinatorial decompositions
- \(O(m\log n)\) split decomposition of strongly-connected graphs
- A faster algorithm for finding minimum Tucker submatrices
- A Representation Theorem for Union-Difference Families and Application
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Cyclic arrangements with minimum modulo \(m\) winding numbers
- Experimental comparison of PC-trees and PQ-trees
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Obtaining matrices with the consecutive ones property by row deletions
- Red-blue covering problems and the consecutive ones property
- Counting the orderings for multisets in consecutive ones property and PQ-trees
- Computing the clique-separator graph for an interval graph in linear time
- Heuristic methods to consecutive block minimization
- A Simple Test for the Consecutive Ones Property
- Bounded Embeddings of Graphs in the Plane
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- Isomorphism of graph classes related to the circular-ones property
- A Simple and Optimal Algorithm for Strict Circular Seriation
- Affine and projective tree metric theorems
- Algorithmic aspects of switch cographs
- Clustered planarity with pipes
- Consecutive ones property testing: cut or swap
- Semi-proper interval graphs
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- A simpler linear-time recognition of circular-arc graphs
- Group control for consent rules with consecutive qualifications
- Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Extending partial representations of circular-arc graphs
- A filter-based algorithm for efficient composition of finite-state transducers
- Filters for Efficient Composition of Weighted Finite-State Transducers
- Fully dynamic representations of interval graphs
- Circular-arc hypergraphs: rigidity via connectedness
- On semi-transitive orientability of split graphs
- Consecutive block minimization is 1.5-approximable
- Normal Helly circular-arc graphs and its subclasses
This page was built for publication: PC trees and circular-ones arrangements.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401263)
