@article{Conte:Kante:Otachi:Uno:Wasa:TCS2018, 
    title    = "Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph",
    journal  = "Theoretical Computer Science",
    year     = "2018",
    issn     = "0304-3975",
    doi      = "10.1016/j.tcs.2018.08.009",
    url      = "http://www.sciencedirect.com/science/article/pii/S0304397518305255",
    author   = "Alessio Conte and Mamadou Moustapha Kanté and Yota Otachi and Takeaki Uno and Kunihiro Wasa",
    keywords = "Graph enumeration, Graph algorithms, Polynomial delay, Degeneracy, Chordal graphs, Clique trees",
    abstract = "In this paper we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m⋅ω(G)) for any n-vertex chordal graph with m edges, where ω(G)≤n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques."
}

{"_id":"ecZamsMkyaWnLJtPA","bibbaseid":"conte-kant-otachi-uno-wasa-efficientenumerationofmaximalkdegenerateinducedsubgraphsofachordalgraph-2018","authorIDs":["552f686310c2c096480000c9"],"author_short":["Conte, A.","Kanté, M. M.","Otachi, Y.","Uno, T.","Wasa, K."],"bibdata":{"bibtype":"article","type":"article","title":"Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph","journal":"Theoretical Computer Science","year":"2018","issn":"0304-3975","doi":"10.1016/j.tcs.2018.08.009","url":"http://www.sciencedirect.com/science/article/pii/S0304397518305255","author":[{"firstnames":["Alessio"],"propositions":[],"lastnames":["Conte"],"suffixes":[]},{"firstnames":["Mamadou","Moustapha"],"propositions":[],"lastnames":["Kanté"],"suffixes":[]},{"firstnames":["Yota"],"propositions":[],"lastnames":["Otachi"],"suffixes":[]},{"firstnames":["Takeaki"],"propositions":[],"lastnames":["Uno"],"suffixes":[]},{"firstnames":["Kunihiro"],"propositions":[],"lastnames":["Wasa"],"suffixes":[]}],"keywords":"Graph enumeration, Graph algorithms, Polynomial delay, Degeneracy, Chordal graphs, Clique trees","abstract":"In this paper we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m⋅ω(G)) for any n-vertex chordal graph with m edges, where ω(G)≤n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques.","bibtex":"@article{Conte:Kante:Otachi:Uno:Wasa:TCS2018, \n title = \"Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph\",\n journal = \"Theoretical Computer Science\",\n year = \"2018\",\n issn = \"0304-3975\",\n doi = \"10.1016/j.tcs.2018.08.009\",\n url = \"http://www.sciencedirect.com/science/article/pii/S0304397518305255\",\n author = \"Alessio Conte and Mamadou Moustapha Kanté and Yota Otachi and Takeaki Uno and Kunihiro Wasa\",\n keywords = \"Graph enumeration, Graph algorithms, Polynomial delay, Degeneracy, Chordal graphs, Clique trees\",\n abstract = \"In this paper we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m⋅ω(G)) for any n-vertex chordal graph with m edges, where ω(G)≤n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques.\"\n}\n\n","author_short":["Conte, A.","Kanté, M. M.","Otachi, Y.","Uno, T.","Wasa, K."],"key":"Conte:Kante:Otachi:Uno:Wasa:TCS2018","id":"Conte:Kante:Otachi:Uno:Wasa:TCS2018","bibbaseid":"conte-kant-otachi-uno-wasa-efficientenumerationofmaximalkdegenerateinducedsubgraphsofachordalgraph-2018","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0304397518305255"},"keyword":["Graph enumeration","Graph algorithms","Polynomial delay","Degeneracy","Chordal graphs","Clique trees"],"downloads":0},"bibtype":"article","biburl":"https://raw.githubusercontent.com/KunihiroWASA/publications_bib/master/publications.bib","creationDate":"2019-09-08T13:16:31.009Z","downloads":0,"keywords":["graph enumeration","graph algorithms","polynomial delay","degeneracy","chordal graphs","clique trees"],"search_terms":["efficient","enumeration","maximal","degenerate","induced","subgraphs","chordal","graph","conte","kanté","otachi","uno","wasa"],"title":"Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph","year":2018,"dataSources":["G5knAh5sDHZjd7TY8"]}