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