PC trees and circular-ones arrangements.
From MaRDI portal
Publication:1401263
DOI10.1016/S0304-3975(02)00435-8zbMath1044.68125OpenAlexW1971080253MaRDI QIDQ1401263
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
Related Items (33)
A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Computing the clique-separator graph for an interval graph in linear time ⋮ Planarity Algorithms via PQ-Trees (Extended Abstract) ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Heuristic methods to consecutive block minimization ⋮ Clustered planarity with pipes ⋮ A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS ⋮ Extending partial representations of circular-arc graphs ⋮ An improved algorithm for the red-blue hitting set problem with the consecutive ones property ⋮ Group control for consent rules with consecutive qualifications ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ On semi-transitive orientability of split graphs ⋮ Algorithmic aspects of switch cographs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Affine and projective tree metric theorems ⋮ Fully dynamic representations of interval graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ \(O(m\log n)\) split decomposition of strongly-connected graphs ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Consecutive block minimization is 1.5-approximable ⋮ A Representation Theorem for Union-Difference Families and Application ⋮ Filters for Efficient Composition of Weighted Finite-State Transducers ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Red-blue covering problems and the consecutive ones property ⋮ Bounded Embeddings of Graphs in the Plane ⋮ Consecutive Ones Property Testing: Cut or Swap ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers
Cites Work
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
- An efficient parallel algorithm for planarity
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A new planarity test
- Incidence matrices and interval graphs
- A Simple Test for the Consecutive Ones Property
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Decomposition of Directed Graphs
- Transitiv orientierbare Graphen
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: PC trees and circular-ones arrangements.