PC trees and circular-ones arrangements.

DOI10.1016/S0304-3975(02)00435-8zbMath1044.68125OpenAlexW1971080253MaRDI QIDQ1401263

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

zbMATH Keywords

PQ trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: PC trees and circular-ones arrangements.