HOME
*





Strongly Chordal Graph
In the mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle. Characterizations Strongly chordal graphs have a forbidden subgraph characterization as the graphs that do not contain an induced cycle of length greater than three or an ''n''-sun (''n'' ≥ 3) as an induced subgraph. An ''n''-sun is a chordal graph with 2''n'' vertices, partitioned into two subsets ''U'' =  and ''W'' = , such that each vertex ''wi'' in ''W'' has exactly two neighbors, ''u''''i'' and ''u''(''i'' + 1) mod ''n''. An ''n''-sun cannot be strongly chordal, because the cycle ''u''1''w''1''u''2''w''2... has no odd chord. Strongly chordal graphs may also be characterized as the graphs having a strong perfect elimination ordering, an ordering o ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Leaf Power
In the mathematical area of graph theory, a -leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induced by the leaves of . For a graph constructed in this way, is called a -leaf root of . A graph is a leaf power if it is a -leaf power for some . These graphs have applications in phylogeny, the problem of reconstructing evolutionary trees. Related classes of graphs Since powers of strongly chordal graphs are strongly chordal and trees are strongly chordal, it follows that leaf powers are strongly chordal graphs. Actually, leaf powers form a proper subclass of strongly chordal graphs; a graph is a leaf power if and only if it is a fixed tolerance NeST graph and such graphs are a proper subclass of strongly chordal graphs. In it is shown that interval graphs and the larger class of rooted directed path graphs are leaf powers. The indif ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Discrete Applied Mathematics
''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split off from another Elsevier journal, ''Discrete Mathematics'', in 1979, with that journal's founder Peter Ladislaw Hammer as its founding editor-in-chief. Abstracting and indexing The journal is abstracted and indexing in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citations of articles published in the last two years in a given journal, as i ... of 1.139. References External links *{{official website, http://www.journals.elsevier.com/discrete-applied-mathematics/ Combinatorics journals Publications established in 1979 Englis ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Journal Of Algorithms
Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', ''Cell'', the ScienceDirect collection of electronic journals, '' Trends'', the '' Current Opinion'' series, the online citation database Scopus, the SciVal tool for measuring research performance, the ClinicalKey search engine for clinicians, and the ClinicalPath evidence-based cancer care service. Elsevier's products and services also include digital tools for data management, instruction, research analytics and assessment. Elsevier is part of the RELX Group (known until 2015 as Reed Elsevier), a publicly traded company. According to RELX reports, in 2021 Elsevier published more than 600,000 articles annually in over 2,700 journals; as of 2018 its archives contained over 17 million documents and 40,000 e-books, with over one billion annual downloads. Researchers have criticized Elsevier for its high profit margin ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


SIAM Journal On Computing
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ''SIAM J. Comput.'', its publisher and contributors frequently use the shorter abbreviation ''SICOMP''. SICOMP typically hosts the special issues of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) and the Annual ACM Symposium on Theory of Computing (STOC), where about 15% of papers published in FOCS and STOC each year are invited to these special issues. For example, Volume 48 contains 11 out of 85 papers published in FOCS 2016. References * External linksSIAM Journal on Computing
on

ACM Transactions On Algorithms
''ACM Transactions on Algorithms'' (''TALG'') is a quarterly peer-reviewed scientific journal covering the field of algorithms. It was established in 2005 and is published by the Association for Computing Machinery. The editor-in-chief is Edith Cohen. The journal was created when the editorial board of the ''Journal of Algorithms'' resigned out of protest to the pricing policies of the publisher, Elsevier. Apart from regular submissions, the journal also invites selected papers from the ''ACM-SIAM Symposium on Discrete Algorithms (SODA)''. Abstracting and indexing The journal is abstracted and indexed in the Science Citation Index Expanded, Current Contents/Engineering, Computing & Technology, and Scopus. According to the ''Journal Citation Reports'', the journal has a 2020 impact factor of 1.104. Past editors The following persons have been editors-in-chief of the journal: * Harold N. Gabow (2005-2008) * Susanne Albers (2008-2014) * Aravind Srinivasan (2014-2021) See a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Information Processing Letters
''Information Processing Letters'' is a peer reviewed scientific journal in the field of computer science, published by Elsevier Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', ''Cell'', the ScienceDirect collection of electronic journals, '' Trends'', th .... The aim of the journal is to enable fast dissemination of results in the field of information processing in the form of short papers. Submissions are limited to nine double-spaced pages. Both theoretical and experimental research is covered. External links * Computer science journals Publications established in 1971 Semi-monthly journals Elsevier academic journals {{compu-journal-stub ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Discrete Mathematics (journal)
''Discrete Mathematics'' is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West ( University of Illinois, Urbana). History The journal was established in 1971. The very first article it published was written by Paul Erdős, who went on to publish a total of 84 papers in the journal. Abstracting and indexing The journal is abstracted and indexed in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor of 0.87. Notable publications * The 1972 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


SIAM Journal On Discrete Mathematics
'' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was established in 1988, along with the ''SIAM Journal on Matrix Analysis and Applications'', to replace the ''SIAM Journal on Algebraic and Discrete Methods''. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.57. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor of 0.755. Although its official ISO abbreviation is ''SIAM J. Discrete Math.'', its publisher and contributors frequently use the shorter abbreviation ''SIDMA''. References External links * Combinatorics journals Publications established in 1988 English-language journals Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way ana ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Split Graph
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have more than one partition into a clique and an independent set; for instance, the path is a split graph, the vertices of which can be partitioned in three different ways: #the clique and the independent set #the clique and the independent set #the clique and the independent set Split graphs can be characterized in terms of their forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle). Relation to other graph families From the definition, split graphs are clearly closed under complementation. Another characterization of split graphs involves complementation: they are chordal graphs the complements of which are also ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Interval Graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning. Definition An interval graph is an undirected graph formed from a family of intervals :S_i,\quad i=0,1,2,\dots by creating one vertex for each interval , and connecting two ver ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Cluster Graph
In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called -free graphs. They are the complement graphs of the complete multipartite graphsCluster graphs
Information System on Graph Classes and their Inclusions, accessed 2016-06-26.
and the 2-leaf powers. The cluster graphs are transitively closed, and every transitively closed undirected graph is a cluster graph.


Related graph classes

Every cluster graph is a