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

zbMATH Keywords

approximation algorithmssimplicial orderinginductive independencecomputing orderingperfectly orientable

Mathematics Subject Classification ID

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)

Network design under general wireless interference

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