Elimination graphs

DOI10.1145/2151171.2151177MaRDI QIDQ3189055zbMATH OpenOpenAlexWikidataFDO

Authors Yuli Ye, Allan Borodin

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2151171.2151177

zbMATH Keywords

approximation algorithmgraph classgreedy algorithmindependent setlocal ratiostructure propertytime complexity

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Elimination Graphs
• Inductive graph invariants and approximation algorithms
• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• On locally optimal independent sets and vertex covers
• Algorithm Theory - SWAT 2004

Cited in

(18)

• Improved algorithms for resource allocation under varying capacity
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Computing inductive vertex orderings
• On tree-constrained matchings and generalizations
• Set cover problems with small neighborhood covers
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Network design under general wireless interference
• Elimination Graphs
• Approximation algorithms for intersection graphs
• Spanning trees with edge conflicts and wireless connectivity
• Inductive graph invariants and approximation algorithms
• The power of oblivious wireless power
• Effective Wireless Scheduling via Hypergraph Sketches
• Bisimplicial separators
• On approximating stochastic independent sets
• Clique cover on L-EPG representations of graphs
• Generalized disk graphs

This page was built for publication: Elimination graphs

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