Computing inductive vertex orderings

DOI10.1016/J.IPL.2021.106159MaRDI QIDQ2234785zbMATH OpenOpenAlexFDO

Authors 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) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Inductive graph invariants and approximation algorithms
• Elimination graphs
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum induced matching algorithms via vertex ordering characterizations
• Approximation algorithms for intersection graphs

Cites work

• Approximation algorithms for intersection graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Elimination graphs
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the Shannon capacity of a graph
• Scheduling Split Intervals
• Simple heuristics for unit disk graphs
• Smallest-last ordering and clustering and graph coloring algorithms
• The sandwich theorem
• Universal framework for wireless scheduling problems

Cited in

(3)

• Vertex ordering with optimal number of adjacent predecessors
• Inductive graph invariants and approximation algorithms
• Network design under general wireless interference

This page was built for publication: Computing inductive vertex orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234785)