The \(k\)-regular induced subgraph problem
From MaRDI portal
Publication:1786867
DOI10.1016/j.dam.2017.01.029zbMath1396.05053WikidataQ57736457 ScholiaQ57736457MaRDI QIDQ1786867
Geir Dahl, Sofia J. Pinheiro, Agostinho Agra, Torkel A. Haufmann
Publication date: 25 September 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2017.01.029
05C35: Extremal problems in graph theory
90C10: Integer programming
90C27: Combinatorial optimization
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
MIP formulations for induced graph optimization problems: a tutorial, Maximum weighted induced forests and trees: new formulations and a computational comparative review, New formulations and branch-and-cut procedures for the longest induced path problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On total unimodularity of edge-edge adjacency matrices
- Improving an upper bound on the size of \(k\)-regular induced subgraphs
- Eigenvalue bounds for independent sets
- Spectral upper bounds for the order of a \(k\)-regular induced subgraph
- Parameterized complexity of finding regular induced subgraphs
- A generalization of antiwebs to independence systems and their canonical facets
- Induced matchings in intersection graphs.
- A lower bound on the independence number of a graph
- Lower bounds on the independence number in terms of the degrees
- An upper bound on the independence number of a graph computable in polynomial-time
- New insights on integer-programming models for the kidney exchange problem
- Maximum \(k\)-regular induced subgraphs
- Laplacian spectral bounds for clique and independence numbers of graphs
- Spectral upper bounds on the size of k-regular induced subgraphs
- On the Shannon capacity of a graph
- Sharp bounds on the order, size, and stability number of graphs
- The Eigenvalues of a Graph and Its Chromatic Number