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