Optimal greedy algorithms for indifference graphs
From MaRDI portal
Publication:2365550
DOI10.1016/0898-1221(93)90308-IzbMath0794.68115MaRDI QIDQ2365550
Stephan Olariu, Peter J. Looges
Publication date: 29 June 1993
Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)
Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10)
Related Items (64)
Greedy algorithms for tracking mobile users in special mobility graphs ⋮ Algorithms for finding disjoint path covers in unit interval graphs ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Coloring problem of signed interval graphs ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Hamiltonian paths, unit-interval complexes, and determinantal facet ideals ⋮ On some subclasses of interval catch digraphs ⋮ Secure domination in proper interval graphs ⋮ Extending partial representations of interval graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ On the thinness and proper thinness of a graph ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Dirac's theorem and multigraded syzygies ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ Acyclic matching in some subclasses of graphs ⋮ Sphere and dot product representations of graphs ⋮ Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ Unnamed Item ⋮ Bandwidth on AT-free graphs ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ The Roberts characterization of proper and unit interval graphs ⋮ Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ A simple algorithm for secure domination in proper interval graphs ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Efficient algorithms for independent Roman domination on some classes of graphs ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ A structural characterization for certifying Robinsonian matrices ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ Unnamed Item ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ Temporal graph classes: a view through temporal separators ⋮ Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Koszul binomial edge ideals of pairs of graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ On central max-point-tolerance graphs ⋮ Total Roman domination for proper interval graphs ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs ⋮ Unnamed Item ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ The co-secure domination in proper interval graphs ⋮ A dynamic distributed approach to representing proper interval graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Characterization of some classes of graphs with equal domination number and isolate domination number ⋮ Clique-width of full bubble model graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs ⋮ Extending partial representations of subclasses of chordal graphs ⋮ Sitting closer to friends than enemies, revisited ⋮ Fragmented coloring of proper interval and split graphs ⋮ Gorenstein binomial edge ideals associated with scrolls
Cites Work
- An optimal greedy heuristic to color interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Semiorders and a Theory of Utility Discrimination
- Representation of a finite graph by a set of intervals on the real line
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A Characterization of Comparability Graphs and of Interval Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Optimal greedy algorithms for indifference graphs
