Computing inductive vertex orderings
DOI10.1016/j.ipl.2021.106159zbMath1476.05154OpenAlexW3173257354MaRDI QIDQ2234785
Magnús M. Halldórsson, Tigran Tonoyan
Publication date: 19 October 2021
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106159
approximation algorithmssimplicial orderinginductive independencecomputing orderingperfectly orientable
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (max. 100)
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation algorithms for intersection graphs
- The sandwich theorem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Elimination graphs
- Smallest-last ordering and clustering and graph coloring algorithms
- On the Shannon capacity of a graph
- Simple heuristics for unit disk graphs
- Scheduling Split Intervals
This page was built for publication: Computing inductive vertex orderings