Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
From MaRDI portal
Recommendations
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- Linear-time recognition of circular-arc graphs
Cited in
(95)- Mutual exclusion scheduling with interval graphs or related classes. I
- A linear time recognition algorithm for proper interval graphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- On the computation of the hull number of a graph
- A dynamic distributed approach to representing proper interval graphs
- Efficient parallel recognition of some circular arc graphs. I
- Optimal circular arc representations: Properties, recognition, and construction
- On chordal proper circular arc graphs
- Satisfiability problems on intervals and unit intervals
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- Tractabilities and intractabilities on geometric intersection graphs
- Unit interval vertex deletion: fewer vertices are relevant
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Normal Helly circular-arc graphs and its subclasses
- Proper interval vertex deletion
- A fully dynamic graph algorithm for recognizing interval graphs
- Completing colored graphs to meet a target property
- Total 2-domination of proper interval graphs
- The hull number in the convexity of induced paths of order \(3\)
- Subclasses of circular-arc bigraphs: Helly, normal and proper
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- On the Carathéodory and exchange numbers of geodetic convexity in graphs
- Extending partial representations of subclasses of chordal graphs
- Fully dynamic recognition of proper circular-arc graphs
- Graphs and digraphs represented by intervals and circular arcs
- On the thinness and proper thinness of a graph
- A dichotomy for minimum cost graph homomorphisms
- The \(k\)-in-a-path problem for claw-free graphs
- Recognition of probe proper interval graphs
- Finding a smallest odd hole in a claw-free graph using global structure
- The Roberts characterization of proper and unit interval graphs
- NP-completeness results for edge modification problems
- On the isomorphism problem for Helly circular-arc graphs
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
- A new representation of proper interval graphs with an application to clique-width
- Proper Interval Vertex Deletion
- Lexicographic orientation algorithms
- On partitioning interval graphs into proper interval subgraphs and related problems
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Partial Characterizations of Circular-Arc Graphs
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- Proper Helly Circular-Arc Graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Random Generation and Enumeration of Proper Interval Graphs
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
- Partial characterizations of circular-arc graphs
- Polynomial kernels for proper interval completion and related problems
- scientific article; zbMATH DE number 140475 (Why is no real title available?)
- On the recognition of fuzzy circular interval graphs
- Coloring fuzzy circular interval graphs
- Random generation and enumeration of bipartite permutation graphs
- A fully dynamic algorithm for the recognition of P₄-sparse graphs
- Computing role assignments of proper interval graphs in polynomial time
- Dynamic algorithms for monotonic interval scheduling problem
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- A superlocal version of Reed's conjecture
- Interval graph representation with given interval and intersection lengths
- A faster algorithm for the cluster editing problem on proper interval graphs
- Claw-free graphs, skeletal graphs, and a stronger conjecture on , , and
- Circularly compatible ones, D-circularity, and proper circular-arc bigraphs
- The Persistent Homology of Cyclic Graphs
- Simultaneous representation of proper and unit interval graphs
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Circular-arc hypergraphs: rigidity via connectedness
- Induced disjoint paths in claw-free graphs
- From a Circular-Arc Model to a Proper Circular-Arc Model
- Powers of cycles, powers of paths, and distance graphs
- Circular-arc bigraphs and its subclasses
- Template-driven rainbow coloring of proper interval graphs
- Template-driven rainbow coloring of proper interval graphs
- Intersection graphs of non-crossing paths
- Extending partial representations of circular-arc graphs
- Recognizing Proper Tree-Graphs
- Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
- Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
- Exactly hittable interval graphs
- On characterization and recognition of proper tagged probe interval graphs
- Modification problems toward proper (Helly) circular-arc graphs
- Simultaneous representation of proper and unit interval graphs
- Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
- Dense and nondense limits for uniform random intersection graphs
- Recognizing and representing proper interval graphs in parallel using merging and sorting
- Some remarks on the geodetic number of a graph
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Obstacle numbers of graphs
- The clique operator on circular-arc graphs
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
This page was built for publication: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4877525)
